Java O(lgN) solution


  • 0
    M
    public class Solution {
        public TreeNode inorderSuccessor(TreeNode root, TreeNode p) {
            if(p != null && p.right != null) {
                TreeNode cur = p.right;
                while(cur.left != null) {
                    cur = cur.left;
                }
                return cur;
            }
            TreeNode next = findNext(root, p);
            return next;
        }
        
        public TreeNode findNext(TreeNode root, TreeNode p) {
            if(root == p) {
                return null;
            }
            if(root.val < p.val) {
                return findNext(root.right, p);
            } else {
                TreeNode left = findNext(root.left, p);
                return findNext(root.left, p) == null ? root : left; 
            }
        }
    }

  • 0

    O(lgN) is impossible. The desired node might be at depth N (I'm assuming with N you mean the number of nodes).


  • 0

    @StefanPochmann this solution is O(log n) only if the tree is balanced correct?? else the solution is O(log h) right?


  • 0

    @mlblount45 That's how I'd say it, yes.


  • 0

    Thanks @StefanPochmann !


  • 0
    Y

    I can not figure out why in the findNext() function, when root==p, we need to return null?
    Thank you


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.