Blog

In Data Structures binary trees is a very important topic. A binary tree is a hierarchical tree-like data structure which contains nodes and at most 2 children. Usually, we call these children left and right children or subtrees.

Terms in Binary Tree

• Root – Top most node of Binary Tree
• Parent – The parent is the node that has almost 2 children
• Child – a child is a descendent of the parent node
• Left and right child – the value of the left child is small than the parent node and the value of the right child is higher than the parent node
• Sub Trees – Left and right also we call left and right subtrees
• Leaf Nodes – The node that does not contains any children is called a leaf node.

Logic for Binary Tree Implementation

• Create a class with a TreeNode name
• Variables of this class include val, left, right
• Val stores the data of node, left reference left child node, right reference right child node.
• Create required constructors for the class

Code for creating Binary Tree

package LeetCodeDebug;

public class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode() {
    }

    TreeNode(int val) {
        this.val = val;
    }

    TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

Using the above constructed binary tree in the below example will give the minimum depth of the binary tree.

Consider the following example to understand it.

Input: root = [3,9,20,null,null,15,7]
Output: 2

package LeetCodeDebug;

import java.util.*;

public class LeetCodeDebug {
    public static void main(String[] args) {

//adding numbers to contruct binary tree
        TreeNode root = new TreeNode(3);
        root.left = new TreeNode(9);
        root.right = new TreeNode(20);
        root.right.left = new TreeNode(15);
        root.right.right = new TreeNode(7);
        System.out.println(minDepth(root));
    }
    public static int minDepth(TreeNode root) {
        if(root==null)
            return 0;
        int left=minDepth(root.left);
        int right=minDepth(root.right);
        if(root.left!=null && root.right!=null)
            return Math.min(left,right)+1;
        return Math.max(left,right)+1;
    }
}