CODEWITHSUNDEEP
algorithmtraversal
nish91
nish91

Reputation: 143

Binary Search Tree In-order traversal without recursion or additional data structures

If nodes in a Binary Search Tree had pointers back to its parent node, is it possible to do an In-order traversal without the need for recursion or additional data structures?

Upvotes: 0

Views: 750

Answers (3)

trincot
trincot

Reputation: 350137

Keep track of the previous node during the traversal, which will help decide which way to go next.

In C#:

class Node {
    /* ... */
    public void inorder() {
        Node curr = this;
        Node prev = null;
        Node next = null;
        while (curr != null) {
            if (curr.right != null && prev == curr.right) {
                next = curr.parent;
            } else if (curr.left == null || prev == curr.left) {
                Console.WriteLine(curr.data);  // <-- visit the node.
                next = curr.right != null ? curr.right : curr.parent;
            } else {
                next = curr.left;
            }
            prev = curr;
            curr = next;
        }
    }
};

In C++ it could look like this:

void inorder(Node* root) {
    Node * curr = root;
    Node * prev = NULL;
    Node * next = NULL;
    while (curr != NULL) {
        if (curr->right != NULL && prev == curr->right) {
            next = curr->parent;
        } else if (curr->left == NULL || prev == curr->left) {
            cout << curr->data << " ";  // <-- visit the node.
            next = curr->right != NULL ? curr->right : curr->parent;
        } else {
            next = curr->left;
        }
        prev = curr;
        curr = next;
    }
    cout << "\n";
}

Upvotes: 2

Phenomenal One
Phenomenal One

Reputation: 2587

Here is a small example.

Map<TreeNode,TreeNode> parent; // available 

Set<TreeNode> set = new HashSet<>(); // maintain visited nodes

TreeNode curr = root;

while(curr!=null){

  if(!set.contains(curr.left) && curr.left!=null){
     curr = curr.left;
  }else if(!set.contains(curr.right) && curr.right!=null){
     System.out.print(curr.value+" ");
     curr = curr.right;
  }else{
     if(curr.right==null){
        System.out.print(curr.value+" ");
     }
     set.add(curr); // mark it as completely visited
     curr = parent.get(curr);
  }
}

Upvotes: 0

Matt Timmermans
Matt Timmermans

Reputation: 59144

To get the first node, you just start at the root and go left as far as possible.

To get from any node to the next:

  • If the node has a right child, then go right, and then go left as far as possible.
  • Otherwise, follow parent pointers up until you get to an ancestor on the right (i.e., you get there from a left child)

You're done when you go up from the root.

Upvotes: 0

Related Questions