What is a Threaded Binary Tree?
Learn what a threaded binary tree is, how it enables O(1) space in-order traversal, and how to answer this interview question.
Expected Interview Answer
A threaded binary tree is a binary tree variant where null left or right child pointers are repurposed as 'threads' pointing directly to the node's in-order predecessor or successor, enabling traversal without recursion or an explicit stack.
In a standard binary tree, roughly half of all pointers in a tree of n nodes are null (n+1 out of 2n pointers, to be exact), which is wasted space. A threaded binary tree replaces those null pointers with links to the in-order predecessor (for null left pointers) or in-order successor (for null right pointers), and typically adds a boolean flag per pointer to distinguish a 'real' child link from a 'thread' link. This makes in-order traversal iterative and O(1) extra space, since from any node you can find the next node in the sequence by following a thread instead of maintaining a stack or parent pointers. Threaded trees come in single-threaded (only right null pointers threaded, for forward traversal) and double-threaded (both directions threaded, enabling traversal in either direction) variants, at the cost of extra bookkeeping on every insert and delete to maintain the threads correctly.
- O(1) space in-order traversal, no stack or recursion needed
- Reuses otherwise-wasted null pointers
- Enables fast predecessor/successor lookup without parent pointers
- Double-threading allows traversal in both directions
AI Mentor Explanation
A threaded binary tree is like a scorecard where every unused slot on a player's card, instead of being left blank, is filled with a note pointing directly to the previous or next batter in the innings order. Normally a blank slot tells you nothing, but here it becomes a shortcut: if a slot has no natural next entry, it instead says 'next batter is over here'. This lets a scorer walk the entire innings order start to finish just by following these notes, without needing a separate list of who bats after whom. The tradeoff is that every substitution requires carefully updating these pointer-notes so they never point to the wrong batter.
Step-by-Step Explanation
Step 1
Identify null pointers
In a binary tree of n nodes, n+1 of the 2n child pointers are null and available to repurpose.
Step 2
Thread null left pointers
Point a node's null left pointer to its in-order predecessor.
Step 3
Thread null right pointers
Point a node's null right pointer to its in-order successor.
Step 4
Tag real vs thread links
Use a boolean flag per pointer so traversal code can tell a real child link from a thread link.
What Interviewer Expects
- Explain that threads replace null pointers with predecessor/successor links
- Distinguish single-threaded vs double-threaded trees
- State the O(1) space benefit for in-order traversal
- Acknowledge the extra bookkeeping cost on insert and delete
Common Mistakes
- Confusing threaded trees with Morris traversal (Morris uses temporary threads; threaded trees keep them permanently)
- Forgetting the boolean flag needed to distinguish a thread from a real child pointer
- Assuming threading speeds up search (it only speeds up traversal, not lookup)
- Not accounting for the extra maintenance cost during insertion and deletion
Best Answer (HR Friendly)
“A threaded binary tree takes all the wasted empty pointers in a normal tree and turns them into shortcuts pointing to the next or previous node in sorted order. That means I can walk through the tree in order without needing a stack or recursion, at the cost of a bit more bookkeeping whenever I insert or delete a node.”
Code Example
class ThreadedNode:
def __init__(self, val):
self.val = val
self.left = None
self.right = None
self.is_thread = False # True if 'right' is a thread, not a real child
def inorder_successor(node):
if node.is_thread:
return node.right
current = node.right
while current and current.left:
current = current.left
return current
def threaded_inorder(root):
result = []
node = root
while node and node.left:
node = node.left
while node:
result.append(node.val)
node = inorder_successor(node)
return resultFollow-up Questions
- How does a threaded binary tree differ from Morris traversal?
- How would double-threading enable both forward and reverse in-order traversal?
- What extra bookkeeping is required when inserting a node into a threaded tree?
- When would a threaded binary tree be preferred over just using an explicit stack for traversal?
MCQ Practice
1. What does a thread in a threaded binary tree replace?
Threads repurpose otherwise-wasted null pointers to point directly to the in-order predecessor or successor.
2. What is the main benefit of a threaded binary tree for in-order traversal?
Threads let traversal jump directly to the next node without maintaining a call stack or explicit stack.
3. What extra field does a threaded binary tree node typically need beyond a normal binary tree node?
Since a null-turned-thread pointer looks structurally the same as a real pointer, a flag is needed to tell them apart during traversal.
Flash Cards
What does a thread in a threaded binary tree point to? — A node's in-order predecessor (left thread) or successor (right thread).
Why are threaded binary trees useful? — They enable O(1) extra space in-order traversal without recursion or a stack.
What is the difference between single- and double-threaded trees? — Single-threaded links only successors (or predecessors) one direction; double-threaded links both directions.
What extra cost does threading add? — Insert and delete operations must carefully maintain the thread pointers, adding bookkeeping overhead.