Trees basics and tree traversals |

Reference : Cracking the coding interview ( Gayle Laakmann Mcdowell )

Trees are the most common graphs seen in coding interviews, and also they are tricky and require additional knowledge such as object oriented programming details.

Very basic node definition in the book is

class Node {
    public String name;
    public Node[] children;
}

or we can implement it something like

public class TreeNode {
      int val;
      TreeNode left;
      TreeNode right;
      TreeNode(int x) { val = x; }
}

if it’s a binary tree.

For tree traversals, there are in-order traversal, pre-order traversal, and post-order traversal.

For in-order traversal, we are visiting the left, the current, and the right branch. The java code is :

void inOrderTraversal(TreeNode node) {
    if (node != null) {
        inOrderTraversal(node.left);
        visit(node);
        inOrderTraversal(node.right);
    }
}

For pre-order traversal :

void inOrderTraversal(TreeNode node) {
    if (node != null) {
        visit(node);    
        inOrderTraversal(node.left);
        inOrderTraversal(node.right);
    }
}

For post-order traversal :

void inOrderTraversal(TreeNode node) {
    if (node != null) {
        inOrderTraversal(node.left);
        inOrderTraversal(node.right);
        visit(node);    
    }
}