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 

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 

Friend Circle - Hackerrank

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

Problem Reference - Hackerrank Problem There are N students in a class. Some of them are friends, while some are not. Their friendship is transitive in nature, i.e., if A is friend of B and B is friend of C, then A is also friend of C. A friend circle is a group of students who are directly or indirectly friends. You are given a N×N−matrix M which consists of characters Y or N. [Read More]
kodeknight  incomplete  hackerrank 

Lazy Caterer's sequence

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

Problem Given a circular (or regular polygon) cake and a knife by which you can only cut vertically, find the maximum number of pieces of cake you can get by making n cuts. Write a program to do that. Solution The solution to this is very simple, if you know mathematics. :P Number of pieces p p = ( n^2+n+2)/2 p = C(n+1,2) + 1 ``` More on wikipedia - [http://en. [Read More]
kodeknight  Interview Question  mathematics 

K reverse a linked list with increasing K

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

Problem Reverse k elements in the linked list such that k goes on increasing Example Eg. 1 - 2 - 3 - 4 - 5 - 6 - 7 output - 1 - 3 - 2 - 6 - 5- 4 - 7 Solution You can take this problem here. Here we are just increasing k. public static ListNode<Integer> reverseSubLinkLists(ListNode<Integer> headerNode) { ListNode<Integer> nextNode = headerNode.next; ListNode<Integer> startNode = null; ListNode<Integer> endNode = null; int k = 2; while (nextNode ! [Read More]
kodeknight  link list  reverse  jabong  Single Link List 

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 

Doubly linked list ADT

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

A doubly-linked list is a linked data structure that consists of a set of sequentially linked records called nodes. Each node contains two fields, called links, that are references to the previous and to the next node in the sequence of nodes. The beginning and ending nodes previous and next links, respectively, point to some kind of terminator, typically a sentinel node or null, to facilitate traversal of the list. If there is only one sentinel node, then the list is circularly linked via the sentinel node. [Read More]
kodeknight  Doubly Linked List  DLL