C# - O(n) in order traversal - collect min diff between visits


  • 0

    If you do an in order traversal you'll be visiting the nodes in sorted order. The min difference will exist between values when sorted.

        public int GetMinimumDifference(TreeNode root) {
            Stack<TreeNode> stack = new Stack<TreeNode>();
            TreeNode curr = root;
            int diff = int.MaxValue;
            int prev = 0;
            bool first = true;
            while (curr != null || stack.Count > 0)
            {
                if (curr != null)
                {
                    stack.Push(curr);
                    curr = curr.left;
                }
                else
                {
                    curr = stack.Pop();
                    if (!first) diff = Math.Min(diff, Math.Abs(prev - curr.val));
                    else first = false;
                    prev = curr.val;
                    
                    curr = curr.right;
                }
            }
            return diff;
        }
    

Log in to reply
 

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