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.
Have you met this question in a real interview?
Yes
Example
Given binary search tree as follow, after Insert node 6, the tree should be:
2 2
/ \ / \
1 4 --> 1 4
/ / \
3 3 6
Challenge
Can you do it without recursion?
public 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.
*/
public TreeNode insertNode(TreeNode root, TreeNode node) {
// write your code here
if(root == null) return node;
TreeNode rootOriginal = root;
while(true){
if(root.val < node.val){
if(root.right == null){
root.right = node;
break;
}
root = root.right;
}else{
if(root.left == null){
root.left = node;
break;
}
root = root.left;
}
}
return rootOriginal;
}
}
Solution 2:
public 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.
*/
public TreeNode insertNode(TreeNode root, TreeNode node) {
// write your code here
if(root == null) return node;
if(root.val > node.val){
if(root.left == null){
root.left = node;
return root;
}
insertNode(root.left, node);
} else {
if(root.right == null){
root.right = node;
return root;
}
insertNode(root.right, node);
}
return root;
}
}
No comments:
Post a Comment