Insert Node in a Binary Search Tree

Question

  1. 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.
  3. Example
  4. Given binary search tree as follow:
  6.      2
  8.   /    \
  10. 1        4
  12.          /
  14.        3
  16. after Insert node 6, the tree should be:
  18.      2
  20.   /    \
  22. 1        4
  24.          /   \
  26.        3        6
  28. Challenge
  29. Do it without recursion

題解 - 遞迴

二元樹的題使用遞迴自然是最好理解的，程式碼也簡潔易懂，缺點就是遞迴調用時stack空間容易溢出，故實際實現中一般使用迭代替代遞迴，性能更佳嘛。不過迭代的缺點就是程式碼量稍(很)大，邏輯也可能不是那麼好懂。

既然確定使用遞迴，那麼接下來就應該考慮具體的實現問題了。在遞迴的具體實現中，主要考慮如下兩點：

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

首先來找找遞迴步，根據二叉查找樹的定義，若插入節點的值若大於當前節點的值，則繼續與當前節點的右子樹的值進行比較；反之則繼續與當前節點的左子樹的值進行比較。題目的要求是返回最終二元搜尋樹的根節點，從以上遞迴步的描述中似乎還難以對應到實際程式碼，這時不妨分析下終止條件。

有了遞迴步，終止條件也就水到渠成了，若當前節點爲空時，即返回結果。問題是——返回什麼結果？當前節點爲空時，說明應該將「插入節點」插入到上一個遍歷節點的左子節點或右子節點。對應到程序程式碼中即爲root->right = node或者root->left = node. 也就是說遞迴步使用root->right/left = func(...)即可。

C++ Recursion

  1. /**
  2.  * forked from http://www.jiuzhang.com/solutions/insert-node-in-binary-search-tree/
  3.  * Definition of TreeNode:
  4.  * class TreeNode {
  5.  * public:
  6.  *     int val;
  7.  *     TreeNode *left, *right;
  8.  *     TreeNode(int val) {
  9.  *         this->val = val;
  10.  *         this->left = this->right = NULL;
  11.  *     }
  12.  * }
  13.  */
  14. class Solution {
  15. public:
  16.     /**
  17.      * @param root: The root of the binary search tree.
  18.      * @param node: insert this node into the binary search tree
  19.      * @return: The root of the new binary search tree.
  20.      */
  21.     TreeNode* insertNode(TreeNode* root, TreeNode* node) {
  22.         if (NULL == root) {
  23.             return node;
  24.         }
  26.         if (node->val <= root->val) {
  27.             root->left = insertNode(root->left, node);
  28.         } else {
  29.             root->right = insertNode(root->right, node);
  30.         }
  32.         return root;
  33.     }
  34. };

Java Recursion

  1. public class Solution {
  2.     /**
  3.      * @param root: The root of the binary search tree.
  4.      * @param node: insert this node into the binary search tree
  5.      * @return: The root of the new binary search tree.
  6.      */
  7.     public TreeNode insertNode(TreeNode root, TreeNode node) {
  8.         if (root == null) {
  9.             return node;
  10.         }
  11.         if (root.val > node.val) {
  12.             root.left = insertNode(root.left, node);
  13.         } else {
  14.             root.right = insertNode(root.right, node);
  15.         }
  16.         return root;
  17.     }
  18. }

題解 - 迭代

看過了以上遞迴版的題解，對於這個題來說，將遞迴轉化爲迭代的思路也是非常清晰易懂的。迭代比較當前節點的值和插入節點的值，到了二元樹的最後一層時選擇是鏈接至左子結點還是右子節點。

C++

  1. /**
  2.  * Definition of TreeNode:
  3.  * class TreeNode {
  4.  * public:
  5.  *     int val;
  6.  *     TreeNode *left, *right;
  7.  *     TreeNode(int val) {
  8.  *         this->val = val;
  9.  *         this->left = this->right = NULL;
  10.  *     }
  11.  * }
  12.  */
  13. class Solution {
  14. public:
  15.     /**
  16.      * @param root: The root of the binary search tree.
  17.      * @param node: insert this node into the binary search tree
  18.      * @return: The root of the new binary search tree.
  19.      */
  20.     TreeNode* insertNode(TreeNode* root, TreeNode* node) {
  21.         if (NULL == root) {
  22.             return node;
  23.         }
  25.         TreeNode* tempNode = root;
  26.         while (NULL != tempNode) {
  27.             if (node->val <= tempNode->val) {
  28.                 if (NULL == tempNode->left) {
  29.                     tempNode->left = node;
  30.                     return root;
  31.                 }
  32.                 tempNode = tempNode->left;
  33.             } else {
  34.                 if (NULL == tempNode->right) {
  35.                     tempNode->right = node;
  36.                     return root;
  37.                 }
  38.                 tempNode = tempNode->right;
  39.             }
  40.         }
  42.         return root;
  43.     }
  44. };

Java Iterative

  1. public class Solution {
  2.     /**
  3.      * @param root: The root of the binary search tree.
  4.      * @param node: insert this node into the binary search tree
  5.      * @return: The root of the new binary search tree.
  6.      */
  7.     public TreeNode insertNode(TreeNode root, TreeNode node) {
  8.         // write your code here
  9.         if (root == null) return node;
  10.         if (node == null) return root;
  12.         TreeNode rootcopy = root;
  13.         while (root != null) {
  14.             if (root.val <= node.val && root.right == null) {
  15.                 root.right = node;
  16.                 break;
  17.             }
  18.             else if (root.val > node.val && root.left == null) {
  19.                 root.left = node;
  20.                 break;
  21.             }
  22.             else if(root.val <= node.val) root = root.right;
  23.             else root = root.left;
  24.         }
  25.         return rootcopy;
  26.     }
  27. }

源碼分析

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