Insert Node in a Binary Search Tree

Description

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.

Notice
You can assume there is no duplicate values in this tree + node.

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?

• we are here

Link

Lintcode_ladder

Method

1. BFS
   • use the characteristic of BST to push node into queue
   • We only condiser finding a proper position to allocate, instead of concern siftup and siftdown or replace some nodes
2. x

Example

1. 1

/**
 * 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) {
        // write your code here
        // input check
        if (!root) {
            return node;
        }
        if (!node) {
            return root;
        }
        // search for the pos of node
        // TreeNode* prev = root;
        queue<TreeNode*> q;
        q.push(root);
        while (!q.empty()) {
            TreeNode* cur = q.front();
            q.pop();
            // locate the position by node->val
            if (cur->val < node->val) {
                if (cur->right) {
                    q.push(cur->right);
                } else {
                    cur->right = node;
                }
            } else {
                if (cur->left) {
                    q.push(cur->left);
                } else {
                    cur->left = node;
                }
            }
        }
        return root;
    }
};

Similar problems

x

Tags

x