In a binary tree, given a root and a number K. You have to find the all nodes at distance K from given root node. For example in a given tree, if K =2 then Output should be 4,5,6 if k = 1 then Output should be 2,3 Time complexity: O(N) as we have to … Read More →
Convert Sorted Linked list to balanced BST
In previous problem, we discussed how to create a balanced binary search tree for a sorted array. Now we’ll see how to create the same from a sorted linked list. Method 1: This solution is similar to our previous solution but unlike array accessing middle element of linked list is not O(1). Approach : i. … Read More →
Convert sorted array to balanced binary search tree
Problem : Given a sorted array . Write a program to create balanced BST from the sorted array. We know that the in-order traversal of binary search tree gives the elements in sorted order. This tells us that the middle element of array will be the root. We can create left and right subtree by … Read More →
Root to leaf path with sum equal to given sum
Given a binary tree and a number,Write a function to find out whether there is a path from root to leaf with sum equal to given Number. In above tree, root to leaf paths exists for following sum. 7=> 1->2->4 9=> 1->3->5 10=>1->3->6 Implementation :
Mirror image of a binary tree
Write a program to create a mirror copy of a binary tree i.e. left nodes become right and right nodes become left. Solution 1 : Following program will create a new mirror tree. Solution 2: This program will convert tree into it’s mirror tree.
Level of a given node in binary tree
Given a Binary Tree and a pointer to the Node in that tree. Write a function to find level of Node in the Tree. For Example, in the below tree 0 / \ 1 4 / \ / \ 2 3 5 6 If the input key … Read More →
Check if a binary tree is subtree of another tree
Given two binary trees T1 and T2, Find whether T2 is a subtree of T1.T1 has millions of nodes and T2 has hundreds of nodes. Solution: Traverse T1 in pre-order fashion. For each node, check if the subtree rooted at this node is identical (exactly same) as T2.
Find largest BST in a binary tree
Given a Binary tree, Find largest Binary Search tree in it. A tree is a BST if: 1. Both left and right subtrees of a node are BSTs. 2. The node’s value is greater than its left subtree’s maximum value. 3. The node’s value is less than its right subtree’s minimum value. Top-Down approach : … Read More →
Binary Tree diff of sum of nodes at odd and sum of nodes at even
Given a Binary Tree, write a function which calculates the difference between the sum of node values at odd levels and sum of node values at even levels. Consider the root node is at height 1. The solution is short and uses recursion. The idea is that you negate all levels under the current one … Read More →
Print all root to leaf paths in a tree
Given a binary tree,Print all root to leaf paths in it. root to leaf paths in above tree. [1 2 4] [1 3 5] [1 3 6] We start with the root and while traversing the tree we keep storing node data in array.We print the array when we reach a leaf node. Time Complexity … Read More →
Diameter of a Tree
Definition : Diameter of a tree is the longest path between two leaf nodes in a tree. We can see in the picture below that Diameter of the tree would be maximum of these: i. Diameter of left subtree. ii. Diameter of right subtree. iii. Path that goes through the root i.e. height of left … Read More →
Replace node with sum of left and right subtree
Given a Binary tree , Replace each node with sum of values in left and right subtree. leaf nodes value will be changed to 0. Solution : i) Traverse the tree recursively. ii) Store the old value of the current node, recursively call for left and right subtrees and change the value of current node … Read More →
What’s going on ?