## Basics
Each Node is connected to at most two Child Nodes.
- Root Node
- Child Node
- Leaf Node (no Child Nodes)
- Ancestor Node
## Types
- Full Binary Tree
- Each Node has 0 or 2 children
- Complete Binary Tree
- All Levels are completely filled except for the last Level
- All Children in the Last Level is all on the left
- Perfect Binary Tree
- All Leaf Nodes are at the same level
- Balanced Binary Tree
- Height of tree is `log_n`
- Degenerate Tree
- Height of tree = n
## Java
```java
class Node {
int data;
Node left;
Node right;
public Node(int key) {
this.data = key;
}
}
public void main() {
Node root = new Node(1);
root.left = new Node(2);
root.right = new Node(3);
root.right.left = new Node(5);
}
```
## Traversals
- Example binary tree [[Drawing 2025-06-16 17.36.49.excalidraw]]
### Depth-first Search
- Inorder traversal
- Inspect *left, root, right*
- *4, 2, 5, 1, 6, 3, 7*
- **in**-order traversal, *root* is **in** between
- Pre-order traversal
- *root, left, right*
- `1, 2, 4, 5, 3, 6, 7`
- **pre** means starts with root
- Post-order travel
- *left, right, root*
- *4, 5, 2, 6, 7, 3, 1*
- **post** means ends with root
### Breadth-first Search
- Go level-by-level
---
## In-order Traversal in Java
```java
class Node {
int data;
Node left;
Node right;
public Node(int key) {
this.data = key;
}
}
public boolean hasChildren(Node node) {
return node.left != null || node.right != null;
}
public List<int> leftRootRight(Node node) {
List<int> list = new ArrayList<int>();
if (node.left != null) {
list.push(node.left.data);
}
if (node.right != null) {
list.push(node.right.data);
}
list.push(node.data);
return data;
}
public List<int> inOrderTraversal(Node node, List<int> dataList) {
// in-order traversal is Left, Root, Right
// if left == null
if (node.left == null) {
dataList.push(node.data);
return inOrderTraversal(node.right);
}
// get left sub-tree
Node leftSubTree = node.left;
if (hasChildren(leftSubTree)) {
dataList = inOrderTraversal(leftSubTree, dataList);
}
if (!hasChildren(node)) {
dataList.push(node.data);
return
}
}
```
## References
- [[Trees (Data Structures)]]
- [[DSA Study MOC]]