Insert Node in a Binary Search Tree

Question

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:

2

/    \

1        4

/

3

after Insert node 6, the tree should be:

2

/    \

1        4

/   \

3        6

Challenge
Do it without recursion


題解 - 遞迴

1. 基本條件/終止條件 - 返回值需斟酌。
2. 遞迴步/條件遞迴 - 能使原始問題收斂。

C++ Recursion

/**
* forked from http://www.jiuzhang.com/solutions/insert-node-in-binary-search-tree/
* Definition of TreeNode:
* class TreeNode {
* public:
*     int val;
*     TreeNode *left, *right;
*     TreeNode(int val) {
*         this->val = val;
*         this->left = this->right = NULL;
*     }
* }
*/
class Solution {
public:
/**
* @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.
*/
TreeNode* insertNode(TreeNode* root, TreeNode* node) {
if (NULL == root) {
return node;
}

if (node->val <= root->val) {
root->left = insertNode(root->left, node);
} else {
root->right = insertNode(root->right, node);
}

return root;
}
};


Java 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) {
if (root == null) {
return node;
}
if (root.val > node.val) {
root.left = insertNode(root.left, node);
} else {
root.right = insertNode(root.right, node);
}
return root;
}
}


題解 - 迭代

C++

/**
* Definition of TreeNode:
* class TreeNode {
* public:
*     int val;
*     TreeNode *left, *right;
*     TreeNode(int val) {
*         this->val = val;
*         this->left = this->right = NULL;
*     }
* }
*/
class Solution {
public:
/**
* @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.
*/
TreeNode* insertNode(TreeNode* root, TreeNode* node) {
if (NULL == root) {
return node;
}

TreeNode* tempNode = root;
while (NULL != tempNode) {
if (node->val <= tempNode->val) {
if (NULL == tempNode->left) {
tempNode->left = node;
return root;
}
tempNode = tempNode->left;
} else {
if (NULL == tempNode->right) {
tempNode->right = node;
return root;
}
tempNode = tempNode->right;
}
}

return root;
}
};


Java Iterative

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 (node == null) return root;

TreeNode rootcopy = root;
while (root != null) {
if (root.val <= node.val && root.right == null) {
root.right = node;
break;
}
else if (root.val > node.val && root.left == null) {
root.left = node;
break;
}
else if(root.val <= node.val) root = root.right;
else root = root.left;
}
return rootcopy;
}
}


源碼分析

NULL == tempNode->right或者NULL == tempNode->left時需要在鏈接完node後立即返回root，避免死循環。

powered by