The Coding Shala

Last Updated: 20-Jan-2021 Home >> Interview Questions >> Connect Nodes at the same level in a binary tree  In this post, we will learn how to Connect nodes at the same level in a binary tree and will implement its solution in Java. Connect nodes at the same level  in a binary tree We have given a perfect binary tree, where each node has an extra pointer called next. The next pointer should point to the node on the right side of it on the same level. This problem is known as connecting nodes at the same level. Given a binary tree:     struct TreeLinkNode {       TreeLinkNode *left;       TreeLinkNode *right;       TreeLinkNode *next;     } Populate each next pointer to point to its next right node. If there is no next right node, the next pointer should be set to NULL. Initially, all next pointers are set to NULL. Example: Given the following perfect binary tree,      ...

Last Updated: 19-Jan-2021 Home >> Data Structures >> Binary Tree Level Order Traversal  In this post, we will learn how to Traverse a Binary Tree in Level Order. Binary Tree Level Order Traversal Given a binary tree, return the level order traversal of its nodes' values. (ie, from left to right, level by level). Example: Given binary tree [3,9,20,null,null,15,7],     3    / \   9  20     /  \    15   7 return its level order traversal as: [   [3],   [9,20],   [15,7] ] Level Order Traversal of Binary Tree in Java Approach 1 Using Queue[BFS]. Iterative Solution. Java Program:  /** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */ class Solution { public List < List < Integer >> levelOrder ( TreeNode root ) { List <...

Last Updated: 19-Jan-2021 Home >> Data Structures >> Binary Tree PostOrder Traversal  In this post, we will learn how to Traverse a Binary Tree in Post-Order. Binary Tree Post-Order Traversal Given a binary tree, return the postorder traversal of its nodes' values. Example: Input: [1,null,2,3]    1     \      2     /    3 Output: [3,2,1] Post-Order Traversal of Binary Tree in Java Approach 1 Using Recursion. Java Program:   /** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */ class Solution { public List < Integer > postorderTraversal ( TreeNode root ) { List < Integer > PostOrder = new ArrayList < Integer >(); if ( root == null ) return PostOrder ; PostOrder . addAll ( postorderTraversal ( root . left )); ...

Last Updated: 19-Jan-2021 Home >> Data Structures >> Binary Tree Inorder Traversal  In this post, we will learn how to Traverse a Binary Tree in In-Order. Binary Tree In-Order Traversal Given a binary tree, return the inorder traversal of its nodes' values. Example: Input: [1,null,2,3]    1     \      2     /    3 Output: [1,3,2] In-Order Traversal of Binary Tree in Java Approach 1 Using Recursion. Java Program:  /** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */ class Solution { public List < Integer > inorderTraversal ( TreeNode root ) { List < Integer > InOrder = new ArrayList < Integer >(); if ( root == null ) return InOrder ; InOrder . addAll ( inorderTraversal ( root . left )); InOrder . add ( ro...

Last Updated: 19-Jan-2021 Home >> Data Structures >> Binary Tree Preorder Traversal  In this post, we will learn how to Traverse a Binary Tree in Pre-Order. Binary Tree Preorder Traversal Given a binary tree, return the preorder traversal of its nodes' values. Example: Input: [1,null,2,3]    1     \      2     /    3 Output: [1,2,3] Preorder Traversal of Binary Tree in Java Approach 1 Using Recursion. Java Program:  /** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */ class Solution { public List < Integer > preorderTraversal ( TreeNode root ) { List < Integer > Pre_Order = new ArrayList < Integer >(); if ( root == null ) return Pre_Order ; Pre_Order . add ( root . val ); Pre_Order . addAll ( preorderTra...

Last Updated: 19-Jan-2021 Home >> Data Structures >> Binary Tree  In this post, we will learn the basic Introduction of Binary Tree Data Structure. Binary Tree A tree is an important data structure to simulate a hierarchical tree structure. In every tree, there will be a root node and a list of references to other nodes which are called child nodes. If a tree has N nodes then there are N-1 edges connecting them. A binary tree is one of the typical tree structure. In a Binary tree, each node has at most two children which are referred to as the left and the right child. How to Traverse a Binary Tree There are many ways to traverse a binary tree. We can traverse a binary tree using BFS and DFS. Using BFS level order traverse Using DFS Pre Order Traversal In Order Traversal Post-Order Traversal We can also use the Recursive and Iterative method to traverse the tree. Recursion is one of the most important methods to traverse the Binary tree. Pre-Order Traver...

Home >> Interview Questions >> Invert Binary Tree In this post, you will learn how to invert the binary tree and will implement a Java program to invert binary tree. Invert Binary Tree Invert the given Binary Tree. Example:  Invert Binary Tree Java Solution What does it mean to invert a binary tree? In a Binary Tree if we swap or interchanges all of its left and right children of all non-leaf nodes then it became an inverted binary tree. Approach 1: We can invert a binary tree using Recursion. We need to swap the left and right nodes of a root node and follow this step recursively for all the nodes. Java Program:  /** * Definition for a binary tree node. * 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 =...

Home >> Interview Questions >> Minimum Depth of a Binary Tree Find Minimum Depth of Binary Tree Given a binary tree, find its minimum depth.  The minimum depth is the number of nodes along the shortest path from the root node down to the nearest leaf node. Note: A leaf is a node with no children. Example: Given binary tree [3,9,20,null,null,15,7],     3    / \   9  20       /  \    15   7 return its minimum depth = 2. Find Minimum Depth of Binary Tree Java Program Method 1: Using recursion. Java Code:  /** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */ class Solution { public int minDepth ( TreeNode root ) { if ( root == null ) return 0 ; if ( root . left == null...

Home >> Interview Questions >> Height of a binary tree Height of a Binary Tree The Binary tree is given you have to find the height of the given binary tree. The height of a binary tree h the number of edges between the tree's root and its furthest leaf. (Maximum depth of a Binary Tree.) Example Height of a Binary Tree Java Program Method 1: Using recursion. Java Code:  public static int height ( Node root ) { // Write your code here. int hi = -1 ; if ( root == null ) return hi ; return 1 + Math . max ( height ( root . left ), height ( root . right )); } Method 2: Using the queue(level order traversal). Java Code:  public static int height ( Node root ) { // Write your code here. int hi = 0 ; if ( root == null ) return hi ; Queue < Node > queue = new LinkedList <>(); ...