首页 > 代码库 > [LintCode] Insert Node in a Binary Search Tree
[LintCode] 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.
You can assume there is no duplicate values in this tree + node.
Given binary search tree as follow, after Insert node 6, the tree should be:
2 2
/ \ / 1 4 --> 1 4
/ / \
3 3 6
Can you do it without recursion?
Solution 1. Recursion
Recursively find the correct subtree of the current processing node to do the insertion. If current node‘s value is bigger than the insert node, go to its left subtree; otherwise go to its right subtree.
Each recursive call returns the new root node after the insertion node is inserted.
1 /** 2 * Definition of TreeNode: 3 * public class TreeNode { 4 * public int val; 5 * public TreeNode left, right; 6 * public TreeNode(int val) { 7 * this.val = val; 8 * this.left = this.right = null; 9 * } 10 * } 11 */ 12 public class Solution { 13 public TreeNode insertNode(TreeNode root, TreeNode node) { 14 if(root == null){ 15 return node; 16 } 17 if(node.val < root.val){ 18 root.left = insertNode(root.left, node); 19 } 20 else{ 21 root.right = insertNode(root.right, node); 22 } 23 return root; 24 } 25 }
Solution 2. Iterative approach
The core idea of inserting a node in BST is to find the "right" place to insert. In solution 1, this place is found by recursively calling the insertNode method.
When the current node is null, it means that the insertion place is just found, return the insertion node as the root node of this null subtree. Each recursive call
returns the new node after inserting node to the subtree.
Alternatively, we can found this insertion place iteratively. The only difference is that we have to do the info booking by ourselves now. Inserting a node essentially
means we need to set a parent node‘s left or right node to the insertion node. As a result, we need to save the parent node of the current processing node. When
the current processing node is null, we found the "right" insertion place. Then we need to check if the node should be inserted to its parent‘s left or right.
1 public class Solution { 2 public TreeNode insertNode(TreeNode root, TreeNode node) { 3 if(root == null){ 4 return node; 5 } 6 TreeNode currNode = root; 7 TreeNode parent = null; 8 while(currNode != null){ 9 parent = currNode; 10 if(node.val < currNode.val){ 11 currNode = currNode.left; 12 } 13 else{ 14 currNode = currNode.right; 15 } 16 } 17 if(node.val < parent.val){ 18 parent.left = node; 19 } 20 else{ 21 parent.right = node; 22 } 23 return root; 24 } 25 }
Related Problems
Remove Node in Binary Search Tree
[LintCode] Insert Node in a Binary Search Tree