Determine if a small tree T2 is the subtree of a huge tree T1

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

You have two very large binary trees: T1, with millions of nodes, and T2, with hundreds of nodes. Create an algorithm to decide if T2 is a subtree of T1. Solution Method 1 - Traversing through T1 and finding subtree at each node, if T1’s node = T2.root Here’s what we will do: Traverse T1.  If the current node is equal to the root node of T2, traverse both of the trees (T2 and the current subtree of T1) at the same time. [Read More]
Binary Tree  BT  kodeknight  CrackingTheCodingInterview 

Given a binary tree with extra field "next pointer" in node, populate the next pointer to the nodes inorder successor

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

Problem : Given a Binary tree where each node has an extra field (node * next), write a function that puts the inorder successor of that node in the next pointer. This is how our binary tree node looks like : struct node { int data; struct node\* left; struct node\* right; struct node\* next; } Initially, all next pointers have NULL values. Your function should fill these next pointers so that they point to inorder successor. [Read More]
inorder  Binary Tree  BT  kodeknight  Amazon  inorder successor  Inorder traversal 

Print nodes at k distance from root

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

Given a root of a tree, and an integer k. Print all the nodes which are at k distance from root. For example, in the below tree, 4, 5 & 8 are at distance 2 from root. 1 / \\ 2 3 / \\ / 4 5 8 Code: void printKDistant(node \*root , int k) { if(root == NULL) return; if( k == 0 ) { printf( "%d ", root->data ); return ; } else { printKDistant( root->left, k-1 ) ; printKDistant( root->right, k-1 ) ; } } Time Complexity: O(n) where n is number of nodes in the given binary tree. [Read More]
Binary Tree  BT  kodeknight  K-Distance  flipkart 

Binary Tree In-Order Traversal - Recursive and Iterative Solution

 Posted on October 5, 2013  (Last modified on August 7, 2020)  |  5 minutes  |  Kinshuk Chandra

Consider the tree Inorder traversal prints the binary tree in increasing order in case of Binary Search Tree, but here we are discussing any binary tree. To traverse a binary tree in Inorder, following operations are carried-out : Traverse the left most subtree starting at the left external node,  Visit the root, and Traverse the right subtree starting at the left external node. Therefore, the Inorder traversal of the above tree will outputs: [Read More]
inorder  Binary Tree  BT  kodeknight  incomplete  Inorder traversal 

Binary tree - Types and Properties

 Posted on August 7, 2013  (Last modified on August 7, 2020)  |  3 minutes  |  Kinshuk Chandra

Tree is sometimes binary tree (BT) and sometimes binary search tree(BST). BT has maximum of 2 child nodes. Binary Search Tree or Ordered tree(sometimes) is BT such that left child has value less than the parent and right child has value greater than parent. Strictly binary tree - If every non-leaf node in BT has non empty left and right subtrees. A / \ B C / \ D E [Read More]
Binary Tree  BT  kodeknight  binary-search-tree  BST 

What is a Complete Binary Tree?

 Posted on July 30, 2013  (Last modified on August 7, 2020)  |  1 minutes  |  Kinshuk Chandra

A strictly binary tree of depth ’d’ in which all the leaves are at level ’d’ i.e. there is non empty left or right subtrees and leaves are populated at the same level. In a complete binary tree all the internal nodes have equal degree, which means that one node at the root level, two nodes at level 2, four nodes at level 3, eight nodes at level 4, etc, which the below figure represents: [Read More]
Binary Tree  BT  kodeknight  binary-search-tree  BST  Data Structure  Complete Binary tree 

Binary tree traversal: Preorder, Inorder, Post-order, BFS, DFS, Level Order, zig zag order

 Posted on July 30, 2013  (Last modified on August 7, 2020)  |  2 minutes  |  Kinshuk Chandra

In order to illustrate the 3 traversals - pre order, in-order and post-order lets take following tree: Preorder traversal: To traverse a binary tree in Preorder, following operations are carried-out (i) Visit the root, (ii) Traverse the left subtree, and (iii) Traverse the right subtree. Therefore, the Preorder traversal of the above tree will outputs: 7, 1, 0, 3, 2, 5, 4, 6, 9, 8, 10 Implementing pre-order traversal [Read More]
inorder  Preorder traversal  Binary Tree  BT  kodeknight  postorder  preorder  incomplete  Inorder traversal  traversal  binary-search-tree  BST  Postorder traversal 

Print a Binary Tree in Zig Zag Level Order or spiral order

 Posted on December 27, 2011  (Last modified on August 7, 2020)  |  4 minutes  |  Kinshuk Chandra

Question: Print a binary tree in zig-zag level order. Zig-zag means print 1st level from left to right, then 2nd level right to left and alternate thereafter. Example: zig-zag level order traversal of below tree will be 0 2 1 3 4 5 6 14 13 12 11 10 9 8 7 Solution1 - Iterative solution Answer: We usually use a queue for level order traversal of a queue. If we want to use the same here, how will we change direction of traversal on every alternate level? [Read More]
tree  Binary Tree  BT  kodeknight  recursion  binary-search-tree  BST  iterative  level-order-traversal 

Vertical Sum of a Binary Tree

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

please explain doubly linked list method in words Anonymous - Apr 6, 2014please explain doubly linked list method in words Added the basic algo for that: 1. Start with the root node and empty double list listNode 2. Add the value of the rootNode to the current listNode 3. Now whenever you go left, pass listNode.left and root.left and call step1 and 2 recursively. 4. Similarly for right node Please let me know if I have not explained it properly. [Read More]
Binary Tree  BT  kodeknight  Amazon  hashmap  Interview Question  hashtable  binary-search-tree  BST  Doubly Linked List  DLL 

Vertical Sum of a Binary Tree

 Posted on December 18, 2011  (Last modified on August 7, 2020)  |  4 minutes  |  Kinshuk Chandra

Question : Find vertical sum of given binary tree. Example: 1 / \\ 2 3 / \\ / \\ 4 5 6 7 The tree has 5 vertical lines Vertical-1: nodes-4 => vertical sum is 4 Vertical-2: nodes-2 => vertical sum is 2 Vertical-3: nodes-1,5,6 => vertical sum is 1+5+6 = 12 Vertical-4: nodes-3 => vertical sum is 3 Vertical-5: nodes-7 => vertical sum is 7 We need to output: 4 2 12 3 7 [Read More]
Binary Tree  BT  kodeknight  Amazon  hashmap  Interview Question  hashtable  binary-search-tree  BST  Doubly Linked List  DLL