Inorder Traverse | Learn for Master
  • 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...]