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.