Skip to interview prep
Apexed

170. What is a threaded binary tree and why would you use one?

MediumTrees

Technical
Show model answer

In a binary tree with n nodes, n + 1 child pointers are null. A threaded tree reuses them: a null right pointer points to the inorder successor and a null left pointer to the inorder predecessor, with a flag bit per pointer to tell a real child from a thread. Single-threaded variants keep only one kind.

Inorder traversal then needs no stack or recursion, and finding a successor is cheap, which helped on memory-constrained systems. The cost is more complex insertion and deletion and the flag bits. Morris traversal is the dynamic cousin: it creates temporary threads during traversal and removes them, giving O(n) time and O(1) extra space on an ordinary tree.

What is a threaded binary tree and why would you use one — Data structures & algorithms interview question — Apexed