卖萌的弱渣

I am stupid, I am hungry.

Insert Node in a Binary Search Tree

Given a binary search tree and a new tree node, insert the node into the tree. You should keep the tree still be a valid binary search tree.

Example

Given binary search tree as follow, after Insert node 6, the tree should be:

1
2
3
4
5

  2             2
 / \           / \
1   4   -->   1   4
   /             / \ 
  3             3   6

Solution

  • Time: O(n)
(Insert-Node-in-a-BST.py) download
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

"""
Definition of TreeNode:
class TreeNode:
    def __init__(self, val):
        self.val = val
        self.left, self.right = None, None
"""
class Solution:
    """
    @param root: The root of the binary search tree.
    @param node: insert this node into the binary search tree.
    @return: The root of the new binary search tree.
    """
    def insertNode(self, root, node):
        # write your code here
        if root == None:
            return node
        if root.val > node.val:
            if root.left == None:
                root.left = node
            else:
                self.insertNode(root.left,node)
        else:
            if root.right == None:
                root.right = node
            else:
                self.insertNode(root.right,node)
        return root