Non-recursive tree traversal in O(n) using constant space

Question (from Introduction to Algorithms by Cormen et al):

Write an O(n)-time non-recursive procedure that, given an n-node binary tree, prints out the key of each node. Use no more than constant extra space outside of the tree itself and do not modify the tree, even temporarily, during the procedure.

Each node has left, child and parent pointers.

Maintain two pointers current and last, to keep track of current node visited and last node visited respectively. Here, I am traversing the list as (parent, left, right) order. Then, depending on the relationship between current node and last node, whether current node is left child or right child or parent, update the current and last pointers accordingly.

last = null;
current = root;
while(current!=null){
	if(last == current.parent){
		print(current.data);
		if(current.left!=null){
				last=current;
				current=current.left;
			}
			else if(current.right!=null){
				last=current;
				current=current.right;
			}
			else{
				last=current;
				current=current.parent;
			}
	} else if(last == current.left){
			if(current.right!=null){
				last=current;
				current=current.right;
			}
			else{
				last=current;
				 current=current.parent;
			}
	} else if(last == current.right){
			last=current;
			current=current.parent;
	}
}

12 thoughts on “Non-recursive tree traversal in O(n) using constant space”

  1. You have come up with really smart algorithm. Thanks for posting this 🙂

    Although, I am not able to understand why it's bounded by O(n). Inside the WHILE loop, you have print() only inside first IF condition and following two ELSE conditions adjust LAST and CURRENT but do not call print(). That means you are not printing a node's value/key on each iteration of while() loop, some of the iterations are used for backtracking. So number of while loop iterations would be greater than n and these extra iterations would depend on length of path from a node to root node.

    Please can you help me understand this ? 🙂

    Thank you,
    Tushar

    1. Hey, I agree the number of iterations will be greater than n but the total number of iterations shall still be some constant factor of n, in fact it will be actually bounded by 2*n.

      I am actually printing the nodes as would have been printed in pre-order traversal of the tree. The logic is that from a given node A, go down in the left subtree of this node A (applying the same logic at each node reached in the subtree) as you can go and then come back to this node A and do the same in the right subtree (applying the same logic at each node reached in the subtree) and then again come back to this node and transfer the control to parent of this current node A.

      So, the number of iterations used for traversing down the left sub-tree would be same as the number of iterations in traversing up back to the node and hence it would be bound by a factor of 2*n, overall. Hope, you were able to follow the logic. If you try running an example using the code present here and print the number of iterations for your sample data, you shall get a more clear picture of the logic.

      1. Thank you very much for explanation.

        At first, I was thinking that we are traveling to each node from root node every time so I was thinking in terms of depth of nodes.

        This is how I have understood it : The number of edges in BST is (n-1) where n is number of nodes. Your algorithm only travels each edge exactly twice so it's bounded by 2*(n-1).

        I have implemented INORDER-WALK(left, parent, right) using only pointers just to get better feel of your approach :


        private void nonRecursiveInOrderWalkUsingPointers(BinaryTreeNode node) {

        BinaryTreeNode prev = null;
        BinaryTreeNode cur = node;

        int count = 0;
        while(cur != null) {
        count++;
        if(prev == cur.parent) { // From parent to right/left child
        if(cur.left != null) {
        prev = cur;
        cur = cur.left;
        } else {
        cur.print();
        if(cur.right != null) {
        prev = cur;
        cur = cur.right;
        } else {
        prev = cur;
        cur = cur.parent;
        }
        }
        }
        else if(prev == cur.left) { // From left child to parent
        cur.print();
        if(cur.right != null) {
        prev = cur;
        cur = cur.right;
        } else {
        prev = cur;
        cur = cur.parent;
        }
        }
        else { // From right child to parent
        prev = cur;
        cur = cur.parent;
        }
        }
        System.out.println("\n Total Iterations : "+count);
        }

        cheers 🙂

  2. Hi all!

    Sorry but I can't understand what will happen on first iteration of the while loop?

    1) If we say that "last" is NULL and "current.parent" is NULL and we assume that null == null will return true, than we will first print root and it's wrong.
    2) Otherwise while loop would be infinite...

    Thanks for answer!

    1. As I specified that I am traversing in the order of (parent, left, right). So, I think first printing root in the first iteration is consistent with the order I expect.

  3. We do not need last pointer if we have parent pointers:
    -------------Here is a java implementation
    public void noneRecursiveTraversWithParentPointer() {

    BSTNode current = mRoot;

    while (current != null) {
    if (current.mLeft != null) {
    current = current.mLeft;
    } else if (current.mRight != null) {
    System.out.println("--data " + current.mData);
    current = current.mRight;
    } else { //leaf
    System.out.println("--data " + current.mData);

    if (current.mParent == null) {
    break;
    }

    //Trace backward to find a node that we can continue go to right
    while ((current.mParent != null) &&
    (current.mParent.mRight == null || current.mParent.mRight == current)) {

    if (current == current.mParent.mLeft) {
    System.out.println("--data " + current.mParent.mData);
    }

    current = current.mParent;
    }

    if (current != null && (current.mParent != null && current.mParent.mRight != null)) {
    System.out.println("--data " + current.mParent.mData);
    current = current.mParent.mRight;
    } else {
    if (current.mParent == null) {
    break;
    }
    }
    }
    }
    }

    class BSTNode {

    public BSTNode(int data, BSTNode parent) {
    mData = data;
    mParent = parent;
    }
    BSTNode mParent;
    BSTNode mLeft;
    BSTNode mRight;
    int mData;
    }

    1. your solution also works fine! 🙂

      However, using one extra pointer variable is still under the limits of using constant space 🙂

  4. Elegant solution. However, there is some redundant code here. I have made some corrections as shown below:

    while(current!=null){
    if(last == current.parent){
    print(current.data);
    last=current;
    if(current.left!=null){
    last=current;
    current=current.left;
    }
    else if(current.right!=null){
    last=current;
    current=current.right;
    }
    else{
    last=current;
    current=current.parent;
    }
    } else if(last == current.left){
    last=current;
    if(current.right!=null){
    last=current;
    current=current.right;
    }
    else{
    last=current;
    current=current.parent;
    }

  5. static void display_preorder_itv(node *head)
    {
    node *prev = head->parent;
    node *tmp = NULL;
    if (!head)
    return;

    while (head)
    {
    if (prev == head->parent)
    printf("%d ", head->data);

    tmp = prev;
    prev = head;

    if (head->left && tmp == head->parent)
    head = head->left;
    else if (head->right && tmp != head->right)
    head = head->right;
    else
    head = head->parent;
    }
    }

    Slight different approach.

  6. Inorder traversal
    static void display_inorder_itv(node *head)
    {
    node *prev = head->parent;
    node *tmp = NULL;
    bool expr = false;
    if (!head)
    return;

    while (head)
    {
    tmp = prev;
    prev = head;

    expr = (head->left && tmp == head->parent) ? true : false;

    if (tmp != head->right && !expr)
    printf("%d ", head->data);

    if (expr)
    head = head->left;
    else if (head->right && tmp != head->right)
    head = head->right;
    else
    head = head->parent;
    }
    }

  7. static void display_postorder_itv(node *head)
    {
    node *prev = head->parent;
    node *tmp = NULL;

    if (!head)
    return;

    if (!head->left && !head->right)
    {
    printf("%d", head->data);
    return;
    }

    while (head)
    {
    tmp = prev;
    prev = head;

    if (head->left && tmp == head->parent)
    head = head->left;
    else if (head->right && tmp != head->right)
    head = head->right;
    else
    {
    if (tmp != head->left)
    printf("%d ", head->data);
    head = head->parent;
    }
    }
    }

    Post Order Approach

Leave a Reply

Your email address will not be published. Required fields are marked *

Notify me of followup comments via e-mail. You can also subscribe without commenting.