Problems based on the Tree data structure

Sheet Link

• Inorder traversal is a depth-first traversal type
• In inorder traversal we follow the Left - Root - Right pattern to traverse the nodes of the binary tree
• So, for each traversal we go to the leftmost node then the root and then the rightmost node
• If we have a Binary tree of height more than 2, we treat each segment of the left and right of the root of binary tree as subtrees.
• Hence until we traverse in-depth at left subtree we won't visit the root and right subtree.
• Java Code (Recursive)

	public static void inorder_traversal(Node root) {
		if (root == null)
			return;

		inorder_traversal(root.left);
		System.out.print(root.data + " ");
		inorder_traversal(root.right);
	}

• Preorder traversal is a depth-first traversal type
• In preorder traversal we follow the Root - Left - Right pattern to traverse the nodes of the binary tree
• So, for each traversal we go to the root, then leftmost node then the rightmost node
• If we have a Binary tree of height more than 2, we treat each segment of the left and right of the root of binary tree as subtrees.
• Hence until we traverse the root we won't visit the left subtree and right subtree.
• Java Code (Recursive)

	public static void preorder_traversal(Node root) {
		if (root == null)
			return;

		System.out.print(root.data + " ");
		preorder_traversal(root.left);
		preorder_traversal(root.right);
	}

• Postorder traversal is a depth-first traversal type
• In postorder traversal we follow the Left - Right - Root pattern to traverse the nodes of the binary tree
• So, for each traversal we go the leftmost node and then the rightmost node only then the root
• If we have a Binary tree of height more than 2, we treat each segment of the left and right of the root of binary tree as subtrees.
• Hence until we traverse in-depth at left subtree and right subtree we won't visit the root.
• Java Code (Recursive)

	public static void postorder_traversal(Node root) {
		if (root == null)
			return;

		postorder_traversal(root.left);
		postorder_traversal(root.right);
		System.out.print(root.data + " ");
	}

• Levelorder traversal is a breadth-first traversal type
• In levelorder traversal we visit each node of the binary tree on a level-wise pattern
• So, for each traversal we go to each level visiting the nodes from left to right
• Here's a pictorial understanding of all of the above traversals

Code Explanation

• To store a given level, we can use queue data structure
• To store level wise order we can use List of List data structure where we store a level in a List and store all lists of levels as a list inside this data structure
• For every level we visit,
  • we will first insert it into the queue
  • next, we take the nodes of current level and check its left and right
  • If left and right exists, we insert the current level of nodes as list inside the answer data structure
  • and insert the left and right we checked into the queue data structure
  • Repeat until left and right is null

Dry Run

• We use root variable to store current node
• Use Arraylist inorder to store inorder traversal answer
• And a Stack stack to store left and right of current nodes
• Insert the root node inside stack first
• Traversal begins
  • Pop the top most node and store it in root variable
  • Store the value of root inside inorder list
  • Using root
    • check if right of root exists and push into stack
    • check if left of root exists and push into stack
  • Continue traversal until stack is empty
• Return inorder list

Dry Run

• We use node variable to store current node
• Use Arraylist inorder to store inorder traversal answer
• And a Stack stack to simulate the auxiliary stack trace used in recursion
• Now the traversal begines
  • If node is not null, push to stack and go the left of node
  • Else check once whether stack is empty
  • Then if node is null, do 2 things
    • Print answer (or) insert the current node's value to answer
    • And go to right of node
  • Repeat the traversal steps until the stack is empty
• Return answer

Dry Run

• There are two approaches to iteratively apply postorder traversal: (1) Using 2 stacks & (2) Using 1 stack

• Initially insert root in stack 1
• Traversal begins:
  • Take the topmost node from stack 1 to insert in stack 2
  • Now, for the topmost node of stack 2, insert left and right in to stack 1
• Once stack 1 is empty, print/return *stack 2 nodes in LIFO order. That's the answer.
• Observation:
  • We try insert root nodes @ stack 2
  • followed by right nodes @ stack 2
  • followed by left nodes @ stack 2
  • In this way we get the correct postorder in stack 2
  • So the stack 2 takes input in reverse of postorder and outputs correct postorder

Dry Run

• At first the root is inserted into the stack
• Take a variable cur to keep track of left nodes
• First we traverse to the left-most node and insert every node we visit in the travsersal into the stack. Basically we are insert every left node from the left subtree.
• Next, when we reach the leftmost node, the cur will become null
• Now, create another variable temp to keep track of the right nodes
• Whenever we reach a leaf node:
  • we pop the top node from stack and add it to postorder
  • Now, we also check whether the popped node (still stored in temp) was right node. If yes, we pop the top node from stack again and add it postorder. We repeat this step until all root nodes of popped nodes are added to postorder.
• Return the answer

Dry Run

• Here we make use of a stack to keep track of each node along with a number
• We make use of a Pair class type to pair up node and number
• Based on the number, we insert each node's value into the preorder/inorder/postorder list
• After every insertion we update this specific number

• Depth/Height of Binary tree can be calculated using recursion
• Here, we can call the depth function recursively for left subtree and right subtree
• We know that the height of the tree will be the maximum of left subtree and right subtree + 1 so that we take only the maximum among subtrees and add 1 to include the root element as well

• Trees are hierarchical data structures, compared with Arrays, Stacks, Queues, Linked lists which are linear data structures
• A hierarchy can be observed in our folder structure

• A tree which can contain at max only two nodes as children is a Binary Tree
• Maximum number of nodes at level i is 2^i
• Maximum number of nodes in a binary tree with height h is 2^h - 1
• Note: Levels in trees start with number 0 and height starts with 1

• Depth-first search (DFS) - Inorder Traversal, Preorder Traversal, Postorder Traversal

• Left - Root - Right

• Root - Left - Right

• Left - Right - Root

• Breadth-first Search (BFS) - Level Order Traversal

1. Generic Tree
2. Binary Tree
3. Binary Search Tree
4. AVL Tree
5. Red-Black Tree
6. N-ary Tree
7. Segment Tree
8. B-tree

• A generic tree is a tree which any node can have any number of children

• Every node in this tree will either have 0 or 2 children
• Example of Full Binary Tree

• All levels are completely filled except the last level
• The last level has all nodes as left as possible
• Example of Complete Binary Tree

• All leaf are at the same level
• Examples of Perfect Binary Tree

• The height of the tree should be at maximum of Log(N), where N is no. of nodes
• Examples of Balanced Binary Tree

• A binary tree, which is dominated solely by left child nodes or right child nodes, is called a skewed binary tree, more specifically left skewed binary tree, or right skewed binary tree.
• Examples of Degenerate/ Skewed Binary Tree