• 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.

    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...]
  • Morris Traversal: Inorder Tree Traversal without recursion and without stack (Java)

    morris inorder traverse example

    Tree traversal is often implemented using Stack or Recursion. In this case, the space complexity is O(h), where h is the height of the tree. We describe a method based on Morris Traversal for tree traversal using O(1) space. 

    The basic idea of Morris Traversal is that: For current Node Cur, we use the right most leaf of its left child to record the location of Cur.

    Suppose we start from root, after running 

    preOfRoot’s right child will point to root. Now we can traverse the left branch of the tree.

    [Read More...]