Skip to main content

Cheat Sheet Binary Tree

Terminologies



Root node - the topmost element is called the root of the binary tree

Leaf Node - the node that does not have any children is the leaf node  

Level of Binary Tree - 

horizontal distance of Binary Tree - 

    horizontal distance of the root is 0

    horizontal distance of the left child = horizontal distance of its parent minus 1

    horizontal distance of the right child = horizontal distance of its parent plus 1 


Predecessor -  

successor  - 





Binary Tree Problems 

1. Inorder traversal  (Left root Right)

while(root != null){

    inorder(root.left)

    print(root.data)

    inorder(root.right)

}



2. Preorder traversal (root Left right )

while(root != null){

    print(root.data)

    preorder(root.left)

    preorder(root.right)

}


3. Postorder traversal (Left right root)

while(root != null){

    postorder(root.left)

    postorder(root.right)

    print(root.data)

}


4.Level order traversal




5. Morris Inorder traversal (left right root)


current = root

previous = null

while(root != null){

    if(root.left == null){

    }else{

        

    }


}




6. Morris Preorder traversal 




7. Left View of Binary Tree

There are two approaches, recursive & iterative approach  



Iterative Approach 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
 ArrayList<Integer> list = new ArrayList<Integer>(); 
    ArrayList<Integer> leftView(Node root)
    {
      leftView(root,0);
      return list;
    }
    
    
    void leftView(Node current, int level){
        
        if(current != null){
            
            if(list.size() == level){
                list.add(current.data);
            }
            
            leftView(current.left, level + 1);
            leftView(current.right, level + 1);
            
        }    
        
      
      
    }

8. Right view of Binary tree 


9. Top view of binary tree

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
class Pair{
    public Node node;
    public int distance;
    
    public Pair(Node node, int distance){
        this.node = node;
        this.distance = distance;
    }
}
    
    
class Solution
{
    

    //Function to return a list of nodes visible from the top view 
    //from left to right in Binary Tree.
    static ArrayList<Integer> topView(Node root)
    {
        ArrayList<Integer> list = new ArrayList<Integer>();
        Queue<Pair> queue = new LinkedList<Pair>();
        TreeMap<Integer,Integer> map = new TreeMap<Integer,Integer>();
        
        Pair firstElement = new Pair(root,0);
        queue.add(firstElement);
        
        while(queue.size() != 0){
            
            Pair pair =  queue.poll();
            Node node = pair.node;
            
            if(!map.containsKey(pair.distance)){
                map.put(pair.distance,node.data); 
            }
            
            
            if(node.left != null){
                queue.add(new Pair(node.left, pair.distance - 1));
            }
            
            if(node.right != null){
                queue.add(new Pair(node.right, pair.distance + 1));
            }
            
        }
        
        for(Integer key : map.keySet()){
            list.add(map.get(key));
        }
        
        return list;   
    }
}


10. Bottom view of Binary Tree

11. LCA - Least Common Ancestor 





Labels:

Comments

Post a Comment

Popular posts from this blog

Hexagonal Architecture (Ports & Adapters Pattern)

Hexagonal Architecture , also known as the Ports and Adapters pattern, is a software design pattern that aims to create a decoupled and maintainable application by separating the core business logic from external concerns (like databases, APIs, and UIs). Structure of Hexagonal Architecture A typical Hexagonal Architecture has three main layers: 1️⃣ Core Domain (Application Logic) This contains the business rules and domain models. It is completely independent of external technologies . Example: If you’re building a banking system , this part would include logic for transactions, withdrawals, and deposits . 2️⃣ Ports (Interfaces) These are interfaces that define how the core interacts with external components. Two types of ports: Inbound Ports (driven by external inputs like APIs, UI, or events) Outbound Ports (used to interact with external services like databases, messaging systems, etc.) 3️⃣ Adapters (Implementation of Ports) These are concrete implementations of the ports, re...
Post a Comment
Read more

Recursion & Choice

Understanding Recursion and Choice Diagrams with Examples Understanding Recursion and Choice Diagrams with Examples Recursion is a powerful concept in programming where a function calls itself to solve smaller instances of the same problem. It's often used in solving complex problems that can be broken down into simpler subproblems. In this blog post, we'll explore the basics of recursion, understand choice diagrams, and see examples to illustrate these concepts. What is Recursion? Recursion occurs when a function calls itself directly or indirectly to solve a problem. A recursive function must have a base case to terminate the recursive calls and prevent infinite recursion. Here's a simple example of a recursive function to calculate the factorial of a number: public class RecursionExample { public static void main(String[] args) { int number = 5; int result = factorial(...
Post a Comment
Read more

Frameworks

  Communication Frameworks: BLUF:  Google's culture strongly emphasizes efficiency and directness, so getting to the "bottom line up front" is very common. SCQA:  Used in presenting proposals, making recommendations, and structuring project plans. PAS : Used in selling ideas and influencing others. BAB : Used in selling ideas and influencing others. Sparklines : Used in presentation to influence others. STAR:  Widely used in Google's interview process and performance evaluations. Problem-Solving/Decision-Making Frameworks: 5 Whys:  A fundamental technique for root cause analysis, and Google is known for its emphasis on data-driven decision-making, which often involves digging into the root causes of problems. Systems Thinking:  Given the complexity of Google's systems, a systems thinking approach is essential. The Four Questions : Used in post-mortem to review an incident. Human factors : Used in post-mortem to avoid the blame culture. Time Management/Prior...
Post a Comment
Read more