Traversing the Binary Search Tree

Question

I was reading through Introduction to algorithms i came across this problem about In-order Traversal of binary search tree without using a stack or recursion. Hint says to assume that testing of pointers for equality is a legitimate operation.I'm stuck finding the solution to this problem. Please give me some direction. I'm not looking for the code. Just give me the right direction.

Exact duplicate here

Answer 1

No stack nor recursion means you have to use pointers. Not giving you code nor the exact answer, since you asked not to :)

Think about how to explore the tree without using recursion: what would you need to do? What pointer(s) do you need to keep? Can a tree node have a pointer to the parent?

Hope it helps.

Answer 2

We need a Threaded Binary Tree to do in-order Traversal without recursion / stack. Wiki says 'A binary tree is threaded by making all right child pointers that would normally be null point to the inorder successor of the node, and all left child pointers that would normally be null point to the inorder predecessor of the node'

So you are given a normal Binary Tree , Convert it into a Threaded Binary Tree which can be done using Morris Traversal. What you are going to do in Morris Traversal is to connect each node with its in-order successor. So while visiting a node ,Search for its in-order predecessor and let it be Pred. then make Pred->right=Current node and we have to revert back the changes too. You can better refer this http://www.geeksforgeeks.org/archives/6358 for a great explanation.

Answer 3

Hello Parminder i have implemented your question in java.Please check it once

class InorderWithoutRecursion {
    public static void morrisTraversal(TreeNode root) {

        TreeNode current,pre;

    if(root == null)
        return; 

    current = root;
    while(current != null){
        if(current.left == null){
            System.out.println(current.data);
            current = current.right;
        }
        else {
      /* Find the inorder predecessor of current */
            pre = current.left;
            while(pre.right != null && pre.right != current)
            pre = pre.right;

      /* Make current as right child of its inorder predecessor */
        if(pre.right == null){
            pre.right = current;
            current = current.left;
        }

      /* Revert the changes made in if part to restore the original
        tree i.e., fix the right child of predecssor */
        else {
            pre.right = null;
            System.out.println(current.data);
            current = current.right;
        }
      } 
  } 
}
 public static void main(String[] args) {
        int[] nodes_flattened = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
        TreeNode root = TreeNode.createMinimalBST(nodes_flattened);
        morrisTraversal(root);
    }
}

For TreeNode class below code will help you..

public class TreeNode {
    public int data;      
    public TreeNode left;    
    public TreeNode right; 
    public TreeNode parent;

    public TreeNode(int d) {
        data = d;
    }

    public void setLeftChild(TreeNode left) {
        this.left = left;
        if (left != null) {
            left.parent = this;
        }
    }

    public void setRightChild(TreeNode right) {
        this.right = right;
        if (right != null) {
            right.parent = this;
        }
    }

    public void insertInOrder(int d) {
        if (d <= data) {
            if (left == null) {
                setLeftChild(new TreeNode(d));
            } else {
                left.insertInOrder(d);
            }
        } else {
            if (right == null) {
                setRightChild(new TreeNode(d));
            } else {
                right.insertInOrder(d);
            }
        }
    }

    public boolean isBST() {
        if (left != null) {
            if (data < left.data || !left.isBST()) {
                return false;
            }
        }

        if (right != null) {
            if (data >= right.data || !right.isBST()) {
                return false;
            }
        }       

        return true;
    }

    public int height() {
        int leftHeight = left != null ? left.height() : 0;
        int rightHeight = right != null ? right.height() : 0;
        return 1 + Math.max(leftHeight, rightHeight);
    }

    public TreeNode find(int d) {
        if (d == data) {
            return this;
        } else if (d <= data) {
            return left != null ? left.find(d) : null;
        } else if (d > data) {
            return right != null ? right.find(d) : null;
        }
        return null;
    }

    private static TreeNode createMinimalBST(int arr[], int start, int end){
        if (end < start) {
            return null;
        }
        int mid = (start + end) / 2;
        TreeNode n = new TreeNode(arr[mid]);
        n.setLeftChild(createMinimalBST(arr, start, mid - 1));
        n.setRightChild(createMinimalBST(arr, mid + 1, end));
        return n;
    }

    public static TreeNode createMinimalBST(int array[]) {
        return createMinimalBST(array, 0, array.length - 1);
    }
}