Question

link

In Binary Tree, Inorder successor of a node is the next node in Inorder traversal of the Binary Tree. Inorder Successor is NULL for the last node in Inoorder traversal.

Write a program with:

1. parent pointer provided
2. parent pointer not provided

Solution

If have parent pointer, it’s easy. Read solution here or [CC150v4] 4.5 Find Next Node in BST.

If no parent pointer, then we make use of the property of BST, can get an O(h) solution. h is the height.

A very good solution from this blog.

1. Start with root.
2. If the node is given has less than root, then search on left side and update successor.
3. If the node is greater than root, then search in right part, don’t update successor.
4. If we find the node
   1. if the node has right sub tree, then the minimum node on the right sub tree of node is the in-order successor.
   2. otherwise, just return successor

The most important point is: we only update successor during left turn, and don’t update during right turn.

Code

written by me

public TreeNode inorderSuccessor(TreeNode root, TreeNode target) {
    if (target.right != null) {
        return this.findLeftMost(target.right);
    } else {
        return this.traverse(root, new TreeNode(-1), target);
    }
}

private TreeNode traverse(TreeNode cur, TreeNode pre, TreeNode target) {
    if (cur.val == target.val) {
        return pre;
    } else if (cur.val < target.val) {
        cur = cur.right;
        return traverse(cur, pre, target);
    } else {
        pre = cur;
        cur = cur.left;
        return traverse(cur, pre, target);
    }
}

private TreeNode findLeftMost(TreeNode node) {
    while (node.left != null) {
        node = node.left;
    }
    return node;
}