Inorder Successor In Binary Search Tree (Ladder)

Description

Given a binary search tree (See Definition) and a node in it, find the in-order successor of that node in the BST. If the given node has no in-order successor in the tree, return null.

Notice:
It's guaranteed p is one node in the given tree. (You can directly compare the memory address to find p)

Example:
Given tree = [2,1] and node = 1:

  2
 /
1
return node 2.

Given tree = [2,1,3] and node = 2:

  2
 / \
1   3
return node 3.

Challenge:
O(h), where h is the height of the BST.

Link

Lintcode_ladder

Method

1. x
2. x

Example

1. 1

   /**
   * Definition for a binary tree node.
   * struct TreeNode {
   *     int val;
   *     TreeNode *left;
   *     TreeNode *right;
   *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
   * };
   */
   class Solution {
   public:
    TreeNode* inorderSuccessor(TreeNode* root, TreeNode* p) {
        // write your code here
        if (!root) {
           return NULL;
        }
        TreeNode* cur = NULL;
        while (root) {
            if (root->val > p->val) {
                cur = root;
                root = root->left;
            } else {
                root = root->right;
            }
        }
        return cur;
    }
   };
   

Similar problems

x

Tags

x