For a Given node of a binary tree, print the K distance nodes.

 Posted on September 4, 2015  (Last modified on August 7, 2020)  |  5 minutes  |  Kinshuk Chandra

Problem You are given a function printKDistanceNodes which takes in a root node of a binary tree, a start node and an integer K. Complete the function to print the value of all the nodes (one-per-line) which are a K distance from the given start node in sorted order. Distance can be upwards or downwards. Example start node = 18, k = 2 , then output = 2, 19, 25 [Read More]
Binary Tree  BT  kodeknight  K-Distance  distance 

Print all nodes that are at distance k from a leaf node

 Posted on September 4, 2015  (Last modified on August 7, 2020)  |  2 minutes  |  Kinshuk Chandra

Problem Given a Binary Tree and a positive integer k, print all nodes that are distance k from a leaf node. Here the meaning of distance is different from previous post. Here k distance from a leaf means k levels higher than a leaf node. For example if k is more than height of Binary Tree, then nothing should be printed. Expected time complexity is O(n) where n is the number nodes in the given Binary Tree. [Read More]
Binary Tree  BT  K-Distance  distance 

Find the distance between 2 nodes in Binary Tree

 Posted on September 4, 2015  (Last modified on August 7, 2020)  |  1 minutes  |  Kinshuk Chandra

cant the solution be simply distance of n1 and n2 …

Rohit Yadav - Feb 0, 2016

cant the solution be simply distance of n1 and n2 from lca.
dist(n1,n2)= dist(lca,n1)+dist(lca,n2)? correct me if i am wrong.

You are absolutely correct. What is being done in the above solution is, dist(n1,n2) = dist(root,n1) + dist(root,n2) - 2*dist(root,lca) as root is point of reference. Thanks.

Binary Tree  BT  kodeknight  least-common-ancestor  LCA  distance 

Find the distance between 2 nodes in Binary Tree

 Posted on September 4, 2015  (Last modified on August 7, 2020)  |  4 minutes  |  Kinshuk Chandra

Problem Find the distance between two keys in a binary tree, no parent pointers are given. Distance between two nodes is the minimum number of edges to be traversed to reach one node from other. Example Dist(-4,3) = 2, Dist (-4,19) = 4 Dist(21,-4) = 3 Dist(2,-4) = 1 Solution The distance between two nodes can be obtained in terms of lowest common ancestor. Following is the formula. Dist(n1, n2) = Dist(root, n1) + Dist(root, n2) - 2\*Dist(root, lca) 'n1' and 'n2' are the two given keys 'root' is root of given Binary Tree. [Read More]
Binary Tree  BT  kodeknight  least-common-ancestor  LCA  distance 

Program to count leaf nodes in a binary tree

 Posted on September 4, 2015  (Last modified on August 7, 2020)  |  1 minutes  |  Kinshuk Chandra

Problem Count leaf nodes in a binary tree Solution Method 1 - Recursive Here is the logic: If node is NULL then return 0. Else If left and right child nodes are NULL return 1. Else recursively calculate leaf count of the tree using below formula. Leaf count of a tree = Leaf count of left subtree + Leaf count of right subtree Here is the recursive solution: [Read More]
Binary Tree  BT  kodeknight  count 

Convert Binary Tree to Doubly linked list in level order

 Posted on May 16, 2015  (Last modified on August 7, 2020)  |  4 minutes  |  Kinshuk Chandra

Question: write an algorithm to convert a binary tree into a double linked list. For example, if the input is the binary tree below: The output will be a double linked list like this: Solution: there are two tasks in converting a binary tree to a linked list. First of all, we must traverse the tree and visit all the nodes. Second of all, we must break each node from the tree and add it into the linked list. [Read More]
conversion  Binary Tree  BT  kodeknight  incomplete  Doubly Linked List  DLL 

Foldable Binary Trees - Given a binary tree, find out if the tree can be folded or not.

 Posted on November 21, 2014  (Last modified on August 7, 2020)  |  2 minutes  |  Kinshuk Chandra

Problem Given a binary tree, find out if the tree can be folded or not. A tree can be folded if left and right subtrees of the tree are structure wise mirror image of each other. An empty tree is considered as foldable. Examples Consider the below trees: (a) and (b) can be folded. (c) and (d) cannot be folded. (a) 10 / \\ 7 15 \\ / 9 11 (b) 10 / \\ 7 15 / \\ 9 11 (c) 10 / \\ 7 15 / / 5 11 (d) 10 / \\ 7 15 / \\ / 9 10 12 Solution Method 1 (Change Left subtree to its Mirror and compare it with Right subtree) [Read More]
Binary Tree  BT  kodeknight 

Given a node in binary tree - Check if left and right subtree are mirror of each other

 Posted on October 18, 2014  (Last modified on August 7, 2020)  |  2 minutes  |  Kinshuk Chandra

Problem A binary tree is a mirror image of itself if its left and right subtrees are identical mirror images i.e., the binary tree is symmetrical. This is best explained with a few examples. Example 1 / \ 2 2 ```TRUE 1 / \ 2 2 \ 3 1 / \ 2 2 / \ / \ 4 3 3 4 1 / \ 2 2 / \ / \ [Read More]
Binary Tree  BT  kodeknight  Amazon 

Check if 2 trees are iso-morphic

 Posted on March 24, 2014  (Last modified on August 7, 2020)  |  1 minutes  |  Kinshuk Chandra

Problem Given 2 binary trees, check if they are isomorphic. Two binary trees s and t are isomorphic if they have the same shape; the values stored in the nodes do not affect whether two trees are isomorphic.  In the diagram below, the tree in the middle is not isomorphic to the other trees, but the tree on the right is isomorphic to the tree on the left. [Read More]
Binary Tree  BT  kodeknight 

Print all paths in a binary tree which sum up to a value

 Posted on March 21, 2014  (Last modified on August 7, 2020)  |  3 minutes  |  Kinshuk Chandra

Problem You are given a binary tree in which each node contains a value. Design an algorithm to print all paths which sum up to that value. Note that it can be any path in the tree – it does not have to start at the root. Example Consider a tree below: 10 / \\ 7 15 / \\ / \\ 8 9 11 1  input value = 16 [Read More]
Binary Tree  BT  kodeknight  CrackingTheCodingInterview