Become Master in Tree

Let me give you a quick introduction about myself.

I'm a 3 year Student studying Computer Science as a major
I'm just an average person like other's.

I'm not talented enough, but I work hard & what I know is "Hard work always beats talent, when talent doesn't work Hard!!”

It's not an language specific article. Trust me, you will learn a lot. Right now it's written in Java but trust me it will never be a issue.

So, with that let's start.
Hello, my fellow programmer's today I'm going to teach you how you can become master's in Tree

If you want to become master, then you have to follow some rules, only after that you can become Magician or called Master's in Tree
Rules:

• Bring up your pen and a fresh new notebook where you have to write all of these thing's which I will teach you right now.
• If you had started learning Tree, then don't quit. Here's why, ask yourself this question when you feel about to quit, "If you had to leave, then why you had start?"
• Look back again at above 2 rule's

Remember : Practice makes a men perfect

													    #Introduction

Let's understand tree with an very basic example:- E.g A family tree

In simple word we can say it is used to explain the hierarchical relationships.

What is Tree?

Tree is a type of a non-linear Data Structure. In this a single node can be connected to multiple nodes..

This hierarchical structure of tree is used in Computer Science as an abstract data type for various applications like data storage, search & sort algorithms.

Basic Term's :-

1. Node
2. Root
3. Children
4. Parent
5. Siblings
6. Ancestor
7. Descendant
8. Leaf

1. Node :- which hold's data eg:- (1)

2. Root :- Where tree start OR top node

3. Children :- it is a node of a parent node. E.g :- (2) is a child of node (1)

4. Parent :- E.g (1) is parent of node (2) & node (3)

5. Siblings :- whose parent is same. E.g (4) & (5) are sibling's because there parent is same i.e. (2)

6. Ancestor :- Going up from a child or leaf

7. Descendant :- Going down from top root

8. Leaf :- is that who don't have any child's E.g (4) & (5) & (6) & (7) are leaf node

Now, What is Binary Tree?

A tree is called binary tree if node has zero, one or two children.

We can visualize a binary tree as consisting of root node, left child & right child.

Types of Binary Trees :-

1. Strict Binary tree
2. Full Binary Tree
3. Complete Binary Tree
4. Skew Binary Tree

1. Strict Binary Tree :- A binary tree is called strict binary tree if each node has exactly teo children or no children.
   

2. Full Binary Tree :- A binary tree in which each node have two children and all the leaf nodes are on the same level.
   

3. Complete Binary Tree :- A binary tree in which all the levels are completely filled except possibly the lowest one, which is filled from the left.
   

4. Skew Binary Tree :- A binary tree in which every parent has exactly one child.
   

Build a tree!!

Let's write a code to build a tree something like this:

Let's see how the recursive call is taking place:

Now, you'll say wait "MALIK" we want to print level by level!!

I'll say okay, for that we will use "Level Order Traversal"!

L1 -->                     (1)
					     /     \
L2 -->                 (2)     (3)
					 /   \    /   \
L3 -->             (4)   (5) (6)  (7)

Something like this, 
first print level-1
then level-2
finally level-3

Explanation:-

• 1st we put (1) in the queue as it's just a root. After that we put it's child in the queue (2) & (3) & pop (1) from the queue & put into arraylist.

• Similarly we put (2) left & right 1st in the queue i.e. (4) & (5) then we put (3) left & right in the queue i.e. (6) & (7)

• Now we check for (4) left & right which is null, similar for (5), (6), (7) which are null as well. We pop them from the queue & put into the arraylist.

• Time Complexity :- BigO(N)

• Space Complexity :- BigO(N)

=> As you see we traverse Iteratively using Queue & get the answer in our list of arraylist.

Solution :-

class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> res = new LinkedList<>();
        Queue<TreeNode> q = new LinkedList<>();
        
        if(root == null) return res;
        
        q.offer(root);
        
        while(!q.isEmpty()){
            int len = q.size();
            List<Integer> subres = new LinkedList<>();
            
            for(int i = 0; i < len; i++){
                if(q.peek().left != null) q.offer(q.peek().left);
                if(q.peek().right != null) q.offer(q.peek().right);
                
                subres.add(q.poll().val);
            }
            res.add(subres);
        }
        return res;
    }
}

Time Complexity :-

Access: O(log(n))
Search: O(log(n))
Insert: O(log(n))
Remove: O(log(n))

                                                        Traversal Technique

So, there are two traversal technique:-

• BFS [ Breadth First Search ]

• DFS [ Depth First Search ]

Let's understand DFS traversal first with an example:

InOrder Traversal (left root right)
First go to left from the root once you reach the left leaf null, add that into your result then traverse it right and so on.
From the above tree the traverse we get is :-

4 2 5   1   6 3 7

PreOrder Traversal (root left right)
First add to the root then go to left from the root once you reach the left leaf null, then traverse it right and so on.
From the above tree the traverse we get is :-

1 2 4   5   3 6 7

PostOrder Traversal (left right root)
First go to left from the root once you reach the left leaf null, then traverse it right and once you reach the null of right now add that value into our result.
From the above tree the traverse we get is :-

4 5 2   6   7 3 1

Trick:- In order to remember these 3 order traversal, remember something like this:

**In**Order --> remember like root in b/w left & right

**Pre**Order --> remember like root before 

**Post**Order --> remember like root in the last 

Now, let's understand BFS traversal with an example:-

=> BFS go level by level

Output:-

1  2  3  4  5  6  7

                                                       Best Question's to practice

Problem list is in order from EASY to HARD in a sequence. And all question's are available on LeetCode!

Tree Data Structure

1. Inorder Traversal of a Binary Tree using Recursion
2. Inorder Traversal of a Binary Tree without Recursion
3. Preorder Traversal of a Binary Tree using Recursion
4. Preorder Traversal of a Binary Tree without Recursion
5. Postorder Traversal of a Binary Tree using Recursion
6. Postorder Traversal of a Binary Tree without Recursion
7. Level Order Traversal of a Binary Tree
8. Reverse Level Order Traversal of a Binary Tree
9. Height of a Binary Tree
10. Mirror of a Tree
11. Invert Binary Tree
12. Cousins in a Binary Tree
13. Left view of a Tree
14. Right view of a Tree
15. Top view of a Tree
16. Bottom view of a Tree
17. Boundary Traversal of a tree
18. Diagonal Traversal of a tree
19. Diameter of a binary Tree
20. LCA of a binary tree
21. Convert binary tree into sum tree
22. Sum root to leaf numbers
23. Path sum
24. Min Depth of binary Tree
25. Check if all leaf nodes are present on the same level or not
26. Check if a binary tree is a subtree of another tree
27. Construct Binary Tree from given inorder and preorder traversal
28. Construct Binary Tree from given inorder and postorder
29. Binary Tree into DLL
30. Kth ancestor of a node in a Binary Tree
31. Check if a tree is balanced or not

Binary Search Tree

1. Find a value in a Binary Search Tree
2. Insertion of a node in a Binary Search Tree
3. Deletion of a node in Binary Search Tree
4. Find minimum value in a Binary Search Tree
5. Find maximum value in a Binary Search Tree
6. Find inorder successor in a Binary Search Tree
7. Find inorder predecessor in a Binary Search Tree
8. Check if a binary tree is a BST or not
9. LCA of 2 nodes in a BST
10. Kth smallest element in a BST
11. Kth largest element in a BST
12. Count pairs from 2 BSTs such that given sum is equal to target
13. Find the median of BST
14. Count BST nodes that lie in a given range
15. Largest BST in a binary tree
16. Flatten BST to sorted linked list
17. Construct BST from preorder traversal
18. Convert BST into balanced BST
19. Merge two BSTs
20. Replace every node with the least greatest node in the BST

I highly recommend you to solve these question's & few of them I will solve as well.

                                                        Recursive Traversal

PreOrder Traversal

144. Binary Tree Preorder Traversal :-

class Solution {
    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        preorder(root, res);
        return res;
    }
    public void preorder(TreeNode root, List<Integer> res){
        if(root == null) return;
        
        res.add(root.val);
        preorder(root.left, res);
        preorder(root.right, res);
    }
}

InOrder Traversal

94. Binary Tree Inorder Traversal :-

class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        inorder(root, res);
        return res;
    }
    public void inorder(TreeNode root, List<Integer> res){
        if(root == null) return;
        
        inorder(root.left, res);
        res.add(root.val);
        inorder(root.right, res);
    }
}

PostOrder Traversal

145. Binary Tree Postorder Traversal :-

class Solution {
    public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        postorder(root, res);
        return res;
    }
    public void postorder(TreeNode root, List<Integer> res){
        if(root == null) return;
        
        postorder(root.left, res);
        postorder(root.right, res);
        res.add(root.val);
    }
}

                                                        Iterative Traversal

PreOrder Traversal

144. Binary Tree Preorder Traversal :-

class Solution {
    public List<Integer> preorderTraversal(TreeNode root) {
        Stack<TreeNode> st = new Stack<>();
        List<Integer> res = new ArrayList<>();
        
        if(root == null) return res;
        
        st.push(root);
        while(!st.isEmpty()){
            root = st.pop();
            res.add(root.val);
            if(root.right != null){
                st.push(root.right);
            }
            if(root.left != null){
                st.push(root.left);
            }
        }
        return res;
    }
}

InOrder Traversal

94. Binary Tree Inorder Traversal :-

class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        Stack<TreeNode> st = new Stack<>();
        List<Integer> res = new ArrayList<>();
        
        TreeNode curr = root;
        
        while(curr != null || !st.isEmpty()){
            while(curr != null){
                st.push(curr);
                curr = curr.left;
            }
            curr = st.pop();
            res.add(curr.val);
            curr = curr.right;
        }
        return res;
    }
}

PostOrder Traversal

145. Binary Tree Postorder Traversal :-

class Solution {
    public List<Integer> postorderTraversal(TreeNode root) {
        Stack<TreeNode> st1 = new Stack<>();
        Stack<TreeNode> st2 = new Stack<>();
        List<Integer> res = new ArrayList<>();
        
        if(root == null) return res;
        st1.push(root);
        while(!st1.isEmpty()){
            root = st1.pop();
            st2.add(root);
            if(root.left != null) st1.push(root.left);
            if(root.right != null) st1.push(root.right);
        }
        while(!st2.isEmpty()){
            res.add(st2.pop().val);
        }
        return res;
    }
}

Alright, guy's I hope you like my work! If do, then stay tuned.

Last Update :- 5th-March-2022