Threaded Binary Tree
Last updated
Last updated
Unlike DFS which adopts recursive algorithms to traverse a tree before backtracking (the stack space of recursive calls would be Ο(n)) and unlike BFS which needs a queue to help traverse the tree level by level, Threaded Binary Tree can achieve traversing a binary tree with only Ο(1) extra space allowed. The traverse method adopting Threaded Binary Tree is also called Morris Traversal.
That said, we do not need to allocate additional memory for each node in the tree. Only using the left and right null pointers of leaves to point to some predecessors or successors would be necessary, which also maintains the original tree structure intact. In a standard Morris traversal algorithm, there is only an in-order version and this chapter only introduces that version. Further modifications could be explored by the users.
Given a binary tree and its root node, the steps of the traversal algorithm includes:
If current node's left child is null, output the current node's value and set its right child as the new current node.
Else if current node's left child is not null, then try to find the predecessor for current node's left subtree in the in-order traversal.
2-1 If the right child of this predecessor is null, set it to current node and update new current node to be the left child of current node.
2-2 Else if the right child of this predecessor is the current node, reset the right child to null (same as recover the original tree structure) and output the current node.
repeat step 1 and 2 until current node is null.
Figure 1. In-order Morris Traversal Demonstration
There are only two additional pointers used, thus requires only Ο(1) for space. Time complexity is Ο(n) since the number of searches for all predecessors of all nodes is bounded by c × n (a binary tree with n nodes has no more then n - 1 nodes, every edge is traversed at most twice).
In the following figure where red dotted lines denote the process of finding such nodes while black dotted lines denote the process of finding predecessors.
Figure 2. Total number of searches
