• LeetCode Recover Binary Search Tree (java)

    Two elements of a binary search tree (BST) are swapped by mistake.

    Recover the tree without changing its structure.

    Note:
    A solution using O(n) space is pretty straight forward. Could you devise a constant space solution?

    Java Solution

    We can use a stack to do an in order traverse of the tree, as it can produce a sorted list of a binary search tree. In the process, we keep track of two pointers pre, cur:

    If we encounter pre.val > cur.val the first time, we get the first error node p1 = pre,

    [Read More...]
  • Leetcode – Maximum Depth of Binary Tree

    Given a binary tree, find its maximum depth.

    The maximum depth is the number of nodes along the longest path from the root node down to the farthest leaf node.

    Analysis:

    This problem can be easily solved using a recursive algorithm.  As

    maxDepth(root) = max(maxDepth(root.left), maxDepth(root.right) + 1 if root != null;

    and maxDepth(root) == 0 if root == null;

    Java solution:

     

    https://leetcode.com/problems/maximum-depth-of-binary-tree/

    [Read More...]
  • LeetCode – Binary Search Tree Iterator (Java)

    Binary Search Tree Iterator

    • Difficulty: Medium

    Implement an iterator over a binary search tree (BST). Your iterator will be initialized with the root node of a BST.

    Calling next() will return the next smallest number in the BST.

    Note: next() and hasNext() should run in average O(1) time and uses O(h) memory, where h is the height of the tree.

    Source: https://leetcode.com/problems/binary-search-tree-iterator/

    In this post, we describe a stack based method to solve the Binary Search Tree Iterator problem in Java. This solution similar to the stack based in oder traversal of a binary search tree. 

    [Read More...]