## Sunday, September 18, 2011

### Depth-First 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.
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;

public class DFSTreeTraversal {

public void mirrorTreeWithOutRecursion(Node root) {

Stack<Node> stack = new Stack<Node>();

stack.push(root);

Node current = null;

while (!stack.isEmpty()) {
current = stack.pop();

// do the processing on a node
process(current);

if (current.left != null)
stack.push(current.left);
if (current.right != null)
stack.push(current.right);
}
return;
}

// process
// example - here we are processing to create mirror of a tree
public void process(Node n) {
Node temp = n.left;
n.left = n.right;
n.right = temp;
}

}

```