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
``````