Trees
Data structures like arrays, linked lists, stacks, and queues come under linear data structures.
In a linear data structure, the data is arranged in a linear or sequential order.
A tree is a non-linear/hierarchical data structure.
Tree Terminologies
https://www.geeksforgeeks.org/introduction-to-tree-data-structure-and-algorithm-tutorials/
Root node: A node with no parent / the node at level 0
Leaf node/external node: Node with no children
Siblings: Children of the same parent node
Edge: Connection between the two nodes
Level of a node: Cound of edges between the node and the root node. The root node has level 0.
Sub-tree: any node and all its descendants
Depth of the tree: the depth of node A is the length of the path from A to the root node. The root node is said to have a depth of 0.
Height of the tree: the height of node A is the length of the longest path through children to a leaf node. The height of the leaf nodes is 0.
Binary Tree
A binary tree is a special type of tree in which each node can have at most 2 nodes. That is, no. of children ≤ 2
class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int data) { this.data = data; }
}The relation between the number of nodes(n) and the height of the tree(H) will not always be H = log₂n. This is because each node can have either 0,1 or 2 children. This means that all the levels are not guaranteed to be completely filled. The tree can be skewed and in the worst case H = n.
skewed: distorted from a true value or symmetrical form
Tree Traversals
- Preorder (Data ‐ Left ‐ Right)
- Inorder (Left ‐ Data ‐ Right)
- Postorder (Left ‐ Right ‐ Data)
Preorder
Leetcode 144. Binary Tree Preorder Traversal
Get Arman Lalani’s stories in your inbox
Join Medium for free to get updates from this writer.
Solution 1: Recursive solution
class Solution {
public List<Integer> preorderTraversal(TreeNode root) {
ArrayList<Integer> ans = new ArrayList<>();
preorder(root, ans);
return ans;
}
static void preorder(TreeNode root, ArrayList<Integer> ans) {
if(root == null) {
return;
}
ans.add(root.val);
preorder(root.left, ans);
preorder(root.right, ans);
}
}Solution 2: Iterative solution using Stack and Pair class
The Stack of Pairs is used to simulate the functional stack. The task number stores the information regarding which line is to be executed next.
class Solution {
public List<Integer> preorderTraversal(TreeNode root) {
LinkedList<Integer> ans = new LinkedList<>();
if (root == null) {
return ans;
}
Stack<Pair> st = new Stack<>();
Pair rootPair = new Pair(root);
st.add(rootPair);
while (!st.isEmpty()) {
Pair top = st.peek();
int task = top.task;
TreeNode node = top.node;
switch (task) {
case 1:
// 1st task: Print the data
ans.add(node.val);
break;
case 2:
// 2nd subtask: Print the LST
if (node.left != null) {
st.add(new Pair(node.left));
}
break;
case 3:
// 3rd subtask: Print the RST
if (node.right != null) {
st.add(new Pair(node.right));
}
break;
case 4:
// 4th subtask: Remove the pair from the stack
st.pop();
}
top.task++;
}
return ans;
}
class Pair {
TreeNode node;
int task = 1;
Pair(TreeNode node) {
this.node = node;
}
}
}Solution 3: Iterative solution using Stack
class Solution {
public List<Integer> preorderTraversal(TreeNode root) {
if(root == null) {
return ans;
}
List<Integer> ans = new LinkedList<>();
Stack<TreeNode> st = new Stack<>();
st.add(root);
while(!st.isEmpty()) {
TreeNode top = st.pop();
ans.add(top.val);
if(top.right != null) {
st.add(top.right);
}
if(top.left != null) {
st.add(top.left);
}
}
return ans;
}
}Inorder
Leetcode 94. Binary Tree Inorder Traversal
Solution 1: Recursive solution and Solution 2: Iterative solution using Stack and Pair class are quite similar to Preorder. We will proceed to discuss the third solution.
Solution 3:
class Solution {
public List<Integer> inorderTraversal(TreeNode root) {
ArrayList<Integer> ans = new ArrayList<>();
if(root == null) {
return ans;
}
TreeNode curr = root;
Stack<TreeNode> st = new Stack<>();
while(curr != null || !st.isEmpty()) {
// Run this loop untill curr becomes null && stack is emptied (curr == null && st.isEmpty())
if(curr == null) {
TreeNode x = st.pop();
ans.add(x.val);
curr = x.right;
} else {
st.push(curr);
curr = curr.left;
}
}
return ans;
}
}Postorder
Leetcode 145. Binary Tree Postorder Traversal
Solution 1: Recursive solution and Solution 2: Iterative solution using Stack and Pair class are quite similar to Inorder and Preorder. We will proceed to discuss the third solution.
Solution 3:
The order of traversal in postorder is left-right-data
Instead, we’ll find the order data-right-left and print it in reverse order.
That is, T(L-R-D) = reverse(T(D-R-L))
This holds true for preorder and inorder too.
class Solution {
public List<Integer> postorderTraversal(TreeNode root) {
List<Integer> ans = new LinkedList<>();
if(root == null) {
return ans;
}
Stack<TreeNode> st1 = new Stack<>();
st1.add(root);
while(!st1.isEmpty()) {
TreeNode top = st1.pop();
ans.addFirst(top.val);
if(top.left != null) {
st1.push(top.left);
}
if(top.right != null) {
st1.push(top.right);
}
}
return ans;
}
}Finding traversal order visually
Traverse the imaginary border around the tree — the grey line.
For preorder, whenever we touch the node from the left side, add it to the answer. For inorder, whenever we touch the node from the bottom, add it to the answer. Similarly for postorder, wherever we touch a node from the right, add it to the answer.
Number of nodes at the last level
Types of Binary Tree
- Proper Binary Tree / Full Binary Tree
Every node has either 0 or 2 children - Complete Binary Tree
All levels are completely filled except possibly the last level
Even if the last level is partially filled, it should be filled from left to right which means there should be no gaps. - Perfect Binary Tree
Every node has 2 children and all leaf nodes are at the same level. - Balanced Binary Tree
The height of the left and right subtrees of any node differs by at most one.
This ensures that the depth of the tree is logarithmic with respect to the number of nodes.
