# Tagged: Trees

## Double Threaded Binary Tree Complete Implementation

In ear­lier arti­cle “Intro­duc­tion to Threaded Binary Tree” we have seen what is threaded binary tree, types of it and what advan­tages it has over nor­mal binary tree. In this arti­cle we will see…

## Single Threaded Binary Tree Complete Implementation

In ear­lier arti­cle “Intro­duc­tion to Threaded Binary Tree” we have seen what is threaded binary tree, types of it and what advan­tages it has over nor­mal binary tree. In this arti­cle we will see…

## Introduction to Threaded Binary Tree

What is Threaded Binary Tree?? A binary tree is threaded by mak­ing all right child point­ers that would nor­mally be null point to the inorder suc­ces­sor of the node (if it exists), and all left child pointers…

## BST to Greater Sum Tree">Convert BST to Greater Sum Tree

Objec­tive: Given a binary search tree (BST), con­vert it into greater sum tree. What is greater sum tree: Greater sum tree is a tree in which every node con­tains the sum of all the nodes…

## Get the Sum of all left leaves in a Binary tree

Objec­tive: Given a binary tree, find the sum of all the nodes which are left as well as leaves nodes. Exam­ple:     Approach: Approach is quite sim­ple. Do the inorder tra­ver­sal check if…

## Convert binary tree to its Sum tree

Objec­tive: Given a binary tree, write an algo­rithm to con­vert it into its Sum tree. What is Sum tree: Sum tree of a binary tree, is a tree where each node in the con­verted tree…

## Binary Tree-Postorder Traversal — Non Recursive Approach

Objec­tive: Given a binary tree, write a non recur­sive or iter­a­tive algo­rithm for pos­torder tra­ver­sal. Exam­ple: Ear­lier we have seen “What is pos­torder tra­ver­sal and recur­sive algo­rithm for it”, In this arti­cle we will…

## Binary Tree — Preorder Traversal — Non Recursive Approach

Objec­tive: Given a binary tree, write a non recur­sive or iter­a­tive algo­rithm for pre­order tra­ver­sal. Exam­ple: Ear­lier we have seen “What is pre­order tra­ver­sal and recur­sive algo­rithm for it”, In this arti­cle we will…

## Binary Tree-Inorder Traversal — Non Recursive Approach

Objec­tive: Given a binary tree, write a non recur­sive or iter­a­tive algo­rithm for Inorder tra­ver­sal. Exam­ple: Ear­lier we have seen “What is Inorder tra­ver­sal and recur­sive algo­rithm for it”, In this arti­cle we will…

## Delete the Binary Tree

Objec­tive: Given a binary tree, write an algo­rithm to delete it. This is one of the basic prob­lem in trees. if you are new to trees then this prob­lem will help you build your…

## Search the Element in a binary tree — With and Without Recursion

Objec­tive: Given a binary tree and a given num­ber x, Write an recur­sive algo­rithm to search the ele­ment in the tree. This is one of the very basic prob­lems of tree. If you are new…

## Tree Traversals

There are mul­ti­ple ways to in which you can tra­verse a tree. In this arti­cle we will see these tra­ver­sals in detail. If you are new to trees then I would rec­om­mend that you…

## Find the Size of a Binary Tree without Recursion

Objec­tive: Given a binary tree, Write an non-recursive algo­rithm to find the size of the tree. Note : Size of the tree is num­ber of nodes in the tree Approach: In our ear­lier post (link) we…

## Breadth-First Search/Traversal in a Binary Tree

Breadth-First Search ( or Tra­ver­sal) also know as Level Order Tra­ver­sal. Exam­ple: What is Breadth First Search: Breadth-first search (BFS) is an algo­rithm for tra­vers­ing or search­ing tree or graph data struc­tures. It starts…

## Merge K Sorted Arrays

Objec­tive: Given k sorted array, write an algo­rithm to merge Them into One sorted array. Exam­ple : int[][] A = new int[5][]; A[0] = new int[] { 1, 5, 8, 9 }; A[1] = new…

## Find the Max element in a Given Binary Tree

Objec­tive: — Given a binary tree , Find the max ele­ment in it. Exam­ple: Approach: Use Recur­sion. Max will the Max(root, max ele­ment in left sub­tree, max ele­ment in right­sub­tree) Recur­sively solve for max element…

## Provide the Next Siblings Pointers in a Given Binary Tree

Objec­tive: — Given a binary tree with three point­ers left, right and nextSi­b­ling). Write the pro­gram to pro­vide the nextsi­b­ling point­ers. Exam­ple: Approach:

## Check If One Binary is Mirror Tree of another Binary Tree.

Objec­tive: — Given two binary trees check if they are mir­ror image of each other. Exam­ple: Approach:

## Print All Paths From Root In a Binary Tree Whose Sum is Equal to a Given Number

Objec­tive: — Given a binary tree and X, Print all the paths start­ing from root so that sum of all the nodes in path equals to a given num­ber. Example:

## Diameter Of a Binary Tree

Objec­tive: — Given a binary tree, find the diam­e­ter of it. What is Diam­e­ter Of a Tree: Diam­e­ter of tree is defined as A longest path or route between any two nodes in a tree.…

## Reverse Level Order Traversal

Objec­tive: — Given a binary tree, Do the reverse level order tra­ver­sal. In our ear­lier post we have seen nor­mal Level Order Tra­ver­sal. In reverse level order tra­ver­sal we first need to print the…

## Find the Deepest Node in a Binary Tree.

Objec­tive: — Given a binary tree, Find the deep­est node in it. Approach: Take two global vari­able as “deep­estlevel” and “value”. start­ing with level=0, Do the inorder tra­ver­sal and when­ever you go down one level…

## Find the Height of a tree without Recursion

Objec­tive: — Find the Height of a tree with­out Recur­sion. In our ear­lier post “Height of tree” we had used recur­sion to find it. In this post we will see how to find it…

## Print All The Full Nodes in a Binary Tree

Objec­tive: Given a binary tree, print all nodes will are full nodes. Full Nodes: Nodes Which has both the chil­dren, left and right are called Full Nodes Approach: quite sim­ple Solu­tion. Do the any of the…

## Binary Min — Max Heap

A binary heap is a heap data struc­ture cre­ated using a binary tree. binary tree has two rules — Binary Heap has to be com­plete binary tree at all lev­els except the last level. This…

## Print the Bottom View of the Binary Tree.

Objec­tive: — Given a binary tree, print it in Bot­tom View of it. What is Bot­tom View: Bot­tom view means when you look the tree from the bot­tom the nodes you will see will be…

## AVL Tree — Insertion">AVL Tree — Insertion

What is AVL Tree : AVL tree is widely known as self-balancing binary search tree. It is named after its cre­ator (Georgy Adelson-Velsky and Lan­dis’ tree). In AVL Tree, the heights of child sub­trees at…

## Construct a binary tree from given Inorder and Level Order Traversal

Objec­tive: — Given a inorder and level order tra­ver­sal, con­struct a binary tree from that. Input: Inorder and level order tra­ver­sal Appraoch: int[] inOrder = { 4, 2, 5, 1, 6, 3, 7 }; int[] levelOrder…

## Construct Binary Search Tree from a given Preorder Traversal Using Stack (Without Recursion)

Objec­tive: — Given a pre­order tra­ver­sal, con­struct BST from that, with­out using recur­sion. Input: Pre­order tra­ver­sal Sim­i­lar Prob­lem : This prob­lem is sim­i­lar to the Con­struct Binary Search Tree from a given Pre­order Traversal…

## Construct Binary Search Tree from a given Preorder Traversal using Recursion

Objec­tive: — Given a pre­order tra­ver­sal, con­struct BST from that. Input: Pre­order tra­ver­sal Sim­i­lar Prob­lem : This prob­lem is sim­i­lar to the — Con­struct Binary Search Tree from a given Pre­order Tra­ver­sal Using Stack (Without…

## Print The Top View of a Binary Tree

Objec­tive: — Given a binary tree, print it in Top View of it. What is Top View: Top view means when you look the tree from the top the nodes you will see will be…

## Construct a Binary Tree from Given Inorder and Depth-First-Search.

Objec­tive: — Given a inorder and pre­order tra­ver­sal, con­struct a binary tree from that. Input: Inorder tra­ver­sal and Depth-First-Search. Approach: int[] inOrder = { 8, 4, 2, 5, 1, 6, 3, 7, 9 }; int[] DFS

## Depth First Search/Traversal in Binary Tree

Objec­tive: — Given a Binary Search Tree, Do the Depth First Search/Traversal . Appraoch: Approach is quite sim­ple, use Stack. First add the add to Stack. Pop out an ele­ment from Stack and add its right…

## Inorder Predecessor and Successor in Binary Search Tree

Objec­tive: — Given a Binary Search Tree, Find pre­de­ces­sor and Suc­ces­sor of a given node. What is Pre­de­ces­sor and Suc­ces­sor : When you do the inorder tra­ver­sal of a binary tree, the neigh­bors of given…

## Print All The Nodes Which are X distance from the Given Node

Objec­tive: — Given Binary Tree, Print All The Nodes Which are X dis­tance from the Given Node. Exam­ple : Appraoch: Quite Tricky solu­tion, i will explain using the exam­ple given in the picture.

## Print All The Nodes Which are X distance from the Leaf Nodes

Objec­tive: — Given Binary Tree, Print All The Nodes Which are X dis­tance from the Leaf Nodes Exam­ple : Approach:

## Print All The Nodes Which are X distance from the Root

Objec­tive: — Given Binary Tree, Print all the nodes which are X dis­tance from the root Exam­ple : Appraoch:

## Find the Distance between Two Nodes of a Binary Tree.

Objec­tive: — Given nodes in a binary tree, find the dis­tance between them. Exam­ple : Approach:

## Find The Distance From Root To Given Node of a Binary Tree.

Objec­tive: — Find The Dis­tance From Root To Given Node of a binary tree. What does Dis­tance means : It means num­ber of edges between two nodes. Approach:

## Construct a binary tree from given Inorder and Postorder Traversal

Objec­tive: — Given a inorder and pos­torder tra­ver­sal, write an algo­rithm to con­struct a binary tree from that. This prob­lem was asked in the Microsoft cod­ing com­pe­ti­tion. Input: Inorder and pos­torder tra­ver­sals Sim­i­lar Problems:…

## Print the Vertical Sum in binary Tree .

Objec­tive: — Given a binary tree, print it in ver­ti­cal order sum What is Ver­ti­cal Order Sum as you can see in the exam­ple above, [4],[2], [12],[3],[7] are the ver­ti­cal order sum of the given binary…

## Print the Binary Tree in Vertical Order Path.

Objec­tive: — Given a binary tree, print it in ver­ti­cal order path. What is Ver­ti­cal Order as you can see in the exam­ple above, [4],[2], [1,5,6],[3],[7] are the ver­i­cal order of the given binary tree. Approach:

## Lowest Common Ancestor in a Binary Tree (Not Binary Search Tree).

Objec­tive: — Find the Low­est Com­mon Ances­tor of two given nodes in a Binary Tree What is Low­est Com­mon Ances­tor In a given binary tree, The low­est com­mon ances­tor of two nodes n1 and…

## Lowest Common Ancestor in a Binary Search Tree.

Objec­tive: — Find the Low­est Com­mon Ances­tor of two given nodes in a Binary Search Tree What is Low­est Com­mon Ances­tor In a given binary tree, The low­est com­mon ances­tor of two nodes n1…

## Make a Binary Tree from Given Inorder and Preorder Traveral.

Objec­tive: — Given a inorder and pre­order tra­ver­sal, con­struct a binary tree from that. Input: Inorder and pre­order tra­ver­sals Sim­i­lar Prob­lem: Con­struct a binary tree from given Inorder and Pos­torder Tra­ver­sal Approach: int [] inOrder…

## Given a binary tree, find out the maximum sum of value from root to each leaf.

Objec­tive: — Find the max­i­mum sum leaf to root path in a Binary Tree. Means in all the paths from root to leaves, find the path which has the max­i­mum sum. Input: A binary tree…

## Reverse Alternate levels of a given Binary Tree.

Objec­tive: — Reverse Alter­nate lev­els of a given binary tree Input: A binary tree Exam­ple: Appraoch:

## Given a Sorted Singly Linked List Array, Convert it into a Balanced Binary search Tree.

Objec­tive: You have been given a sorted singly List, you need to con­vert it into bal­anced binary search tree. Why bal­anced binary tree is impor­tant: You can also cre­ate first node as root and…

## Given a binary tree, Convert it into its Mirror Tree

Objec­tive: Given a binary tree, Con­vert it into its Mir­ror Tree Mir­ror Tree: Mir­ror Tree of a binary tree is where left and right child of every node of given binary tree is interex­changed. Input:…

## Given a binary tree, Print All the Nodes that don’t have Siblings.

Objec­tive: Given a binary tree, Print All the Nodes that don’t have sib­lings. Note: sib­ling node is the node which has the same par­ent, so you need to print the nodes who is a…