## Sunday, September 18, 2011

### InOrder Binary Tree Traversal

Time Complexity - O ( n log n )
Space Complexity - O ( n log n )

For every element to be processed, we keep looping down till we reach the leaf child node. And then elements are processed while coming up.

For an element to be at depth d, we have to do do d amount of work to reach that element. Then process it.

Thus to process element n, we recursively loop (or loop to stack the elements) upto height of that node O(h)
Since going down by height, we divide the scope into half (left or right subtree) - O(h) is log n
And each time we loop (through recursion or stack) - a new layer of stack is allocated in memory

Thus for all elements -
Time & Space Complexity = nO(h) = nlog n = n log n

Any tree traversal - Inorder, PreOrder, PostOrder, BFS, DFS - are all same O(n log n)

```package main.java.algo.datastructures.binarytree.traversal;

import java.util.Stack;

import main.java.algo.datastructures.binarytree.Node;

/**
** Given a binary search tree (aka an "ordered binary tree"),
** iterate over the nodes to print them out in increasing order.
**
** So the tree...
4
/ \
2   5
/ \
1   3
/
0.5

** Produces the output "0.5 1 2 3 4 5".
**
** This is known as an "inorder" traversal of the tree.
**
**/

public class InOrder {

/** ************************** InOrder : Recursive ************************** **/

//For each node, the strategy is: recur left, print the node data, recur right.
public void inOrderRecursive(Node node) {

if (node == null)
return;

// left, node itself, right

if (node.left != null)
inOrderRecursive(node.left);

System.out.println(node.data);

if (node.right != null)
inOrderRecursive(node.right);

}

/** ************************** InOrder : Iterative ************************** **/

public void inOrderIterative (Node n) {

//using stack
Stack<Object> s = new Stack<Object>();

// what inOrderRecursive(n.left) does
inOrderPushLeftChildsToStack(s, n);

// what happens when inOrderRecursive(n.right) is called
while (!s.isEmpty()) {

Node t = (Node) s.pop();

// processing on a node
process(t);

// inOrderRecursive(n.right) is called
t = t.right;
// what inOrderRecursive(n.left) does
inOrderPushLeftChildsToStack(s, t);
}
}

// it does what inOrderRecursive(n.left) was doing
public void inOrderPushLeftChildsToStack(Stack<Object> s, Node n) {
while (n != null) {
s.push(n);
n = n.left;
}
}

public void process(Node n) {
System.out.println(n.data);
}

}

```