Data Structures

Tree

  • A Tree is a structure composed of Nodes
  • Every Node has zero or more children Nodes
  • Can not contain cycles
  • Can be in a particular order or not
  • Nodes can have links back to their parents or not
  • A Node is called a Leaf if it has no children

Binary Tree

  • A Binary Tree is a Tree where each node has zero, one or two children

Binary Search Tree

  • A Binary Search Tree is a Tree where all values on left hand-side children are smaller than all right hand-side children
     6
   /   \
  4     8
 / \   / \ 
3  5  7   9

- Binary Search Tree Example 

Binary Tree Traversal

In Order Traversal

  • Visit left hand-side
  • Visit node itself
  • Visit right hand-side
class Node<T> {
    T val;
    Node<T> left;
    Node<T> right;
}

static void inOrderTraversal(Node n) {
    if (n == null) {
        return;
    }
    inOrderTraversal(n.left);
    System.out.print(n.val + " ");
    inOrderTraversal(n.right);
}

// Create tree
Node<Integer> _10 = new Node<>();
_10.val = 10;

Node<Integer> _5 = new Node<>();
_5.val = 5;

Node<Integer> _20 = new Node<>();
_20.val = 20;

Node<Integer> _9 = new Node<>();
_9.val = 9;

Node<Integer> _18 = new Node<>();
_18.val = 18;

Node<Integer> _3 = new Node<>();
_3.val = 3;

Node<Integer> _7 = new Node<>();
_7.val = 7;

_10.left = _5;
_5.left = _9;
_5.right = _18;

_10.right = _20;
_20.left = _3;
_20.right = _7;

//      10
//    /    \
//   5      20
//  / \    /  \ 
// 9  18  3    7 

// In - Order Traversal 
inOrderTraversal(_10);
// Prints: 9 5 18 10 3 20 7