Inorder Traversal (DFS) using Constant Space 😍 instead of O(height) 💩

This is a coding interview problem that Palantir asked.

Description

"Given a binary tree, perform an inorder traversal without using the normal O(height) space complexity approach. Do it using O(1) space."

Many of us are aware of two methods for the inorder traversal of a tree.

• Recursion: Uses O(h) space in the call stack.
• Iterative: Uses a stack to keep track of the path from the current node to root, which can grow up to the tree's height.

Why do we need space for this problem?

The critical thing to ask yourself is, why were we using any space?

And the answer is, we need space to save a node to come back to it after traversing its left subtree.

Be it stack or recursion, we process a subtree and, using pop in a stack or returning from a recursive call, reach to its parent and traverse the right subtree.

It means if we can somehow move from the last node of a left subtree (rightmost child) to the parent, then we will not need to save the parent.

The Solution

The trick is to use pointers to point to the node that should be visited next after a subtree is processed.

Let's see it using a simple example.

We start with the root (4), and as it is an inorder traversal, we will process the left subtree before processing the current root.

But now we have a problem; in other approaches, we were using a data structure or recursion to store the current node before moving on to the left subtree so that we can come back to it after the left subtree is traversed.

The solution is to create a link from the last node of the left subtree (rightmost node) to the current node before processing the left subtree. In this way, we won't be needing to save anything.

The algorithm for the traversal:

• Perform the following steps till the current node is not null.
• Start with the root node as the current node and check if its left subtree is present.
• If not present, print the current node and make its right child as the current node.
• If present, then first find the last node of the left subtree and (if it is not already pointing to the current node) then make its right pointer to point to the current node and then make the left child of the current node as the current node.
• And, if the right child of the last node of a subtree is already pointing to the current node, it means we have traversed the subtree, then print the current node and traverse the right subtree.

Let's traverse the above tree now using the algorithm to make things clear.

The current node is the root node (4); we find the rightmost node of the left subtree and point it to the current node. Hence, 2's right pointer is pointing to 4.

Now, 3 is the current node, and since its left subtree is not empty, we will find the rightmost child (7) and make its right pointer to point to 3. Node 7 is the current node.

Since 7 has an empty left subtree, we print the current node [7] and move to its right child, making node 3 the current node. We again check if its left subtree is not empty and find the rightmost child of its left subtree.

But this time, the right child of the last node and the current node are the same; hence, print the current node [7 3], delete the pointer and move to its right child (node 2).

We can see that the left child of node 2 is not present, so we print the current node [7 3 2] and move to its right child, which is 4.

Again, since the left subtree of 4 is not empty, we will find the last node of its left subtree. And we can see that the right child of the last node is the current node (4). So, we will remove this pointer from 2 to 4 and print the current node [7 3 2 4] before moving to the right child (1).

Finally, we can see that the left child of 1 is missing, so we print the current node [7 3 2 4 1] and move to its right child, which is null, and we end the process.

Now, Let's look at the code 🤩.

The Code

The Output:

7 3 2 4 1

The time and Space complexity

Time: We traverse every node twice, once while finding the last node of the left subtree and another while traversing the subtree. Hence, the complexity is O(n).

Space: We are not using any data structure or recursion for getting back to the parent node of a subtree; hence the space complexity is constant.

P.S.: If you like this uninterrupted reading experience on this beautiful platform of Medium.com, consider supporting the writers of this community by signing up for a membership HERE. It only costs $5 per month and helps all the writers.

If you liked what you just read, a clap would be highly appreciated. You can be generous in clapping; it shows me how much you enjoyed this story. And if you didn't like it? Please do comment😋!

You can also follow me HERE to get updates on the stories that I write.