Check whether binary tree are same or not?

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

Problem Given two binary trees, return true if they are structurally identical – they are made of nodes with the same values arranged in the same way. Solution 11\. sameTree() Solution (C/C++) /\* Given two trees, return true if they are structurally identical. \*/ int isIdentical(struct node\* a, struct node\* b) { // 1. both empty -> true if (a==NULL && b==NULL) return(true); // 2. both non-empty -> compare them else if (a! [Read More]
tree  kodeknight  identical  binary-search-tree  BST  check 

Double the tree such that insert new duplicate node for each node using cpp

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

Problem For each node in a binary search tree, create a new duplicate node, and insert the duplicate as the left child of the original node. The resulting tree should still be a binary search tree. So the tree… 2 / \ 1 3 is changed to… 2 / \ 2 3 / / 1 3 / 1 As with the previous problem, this can be accomplished without changing the root node pointer. [Read More]
tree  kodeknight  duplicate  binary-search-tree  BST 

Given a BST, create a mirror of it.

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

Problem Change a tree so that the roles of the left and right pointers are swapped at every node. Example So the tree… 4 / \ 2 5 / \ 1 3 is changed to… 4 / \ 5 2 / \ 3 1 The solution is short, but very recursive. As it happens, this can be accomplished without changing the root node pointer, so the return-the-new-root construct is not necessary. [Read More]
tree  kodeknight  mirror  recursion  binary-search-tree  BST  iterative 

Given Binary Tree and sum, give root to leaf path such that all nodes add to that sum

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

We’ll define a “root-to-leaf path” to be a sequence of nodes in a tree starting with the root node and proceeding downward to a leaf (a node with no children). We’ll say that an empty tree contains no root-to-leaf paths. So for example, the following tree has exactly four root-to-leaf paths: 5 / \\ 4 8 / / \\ 11 13 4 / \\ \\ 7 2 1 ```Root-to-leaf paths: path 1: 5 4 11 7 path 2: 5 4 11 2 path 3: 5 8 13 path 4: 5 8 4 1 For this problem, we will be concerned with the sum of the values of such a path -- for example, the sum of the values on the 5-4-11-7 path is 5 + 4 + 11 + 7 = 27. [Read More]
tree  kodeknight  path  binary-search-tree  BST 

Print binary search tree in increasing order

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

Given a binary search tree (aka an “ordered binary tree”), iterate over the nodes to print them out in increasing order. So the tree… 4 / \ 2 5 / \ 1 3 Produces the output “1 2 3 4 5”. This is known as an “inorder” traversal of the tree. Hint: For each node, the strategy is: recur left, print the node data, recur right. Here is code in c/cpp: [Read More]
inorder  tree  kodeknight  traversal  binary-search-tree  BST 

Find the minimum data value find in Binary Search tree (using cpp)

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

Given a non-empty binary search tree (an ordered binary tree), return the minimum data value found in that tree. Note that it is not necessary to search the entire tree. A maxValue() function is structurally very similar to this function. This can be solved with recursion or with a simple while loop. int minValue(struct node* node) { /\* Given a non-empty binary search tree, return the minimum data value found in that tree. [Read More]
tree  kodeknight  binary-search-tree  BST  min 

Compute Maximum Depth or Height of binary search tree

 Posted on May 11, 2011  (Last modified on August 7, 2020)  |  3 minutes  |  Kinshuk Chandra

Given a binary tree, compute its “maxDepth” – the number of nodes along the longest path from the root node down to the farthest leaf node. The maxDepth of the empty tree is 0, the maxDepth of the tree below is 3.  1 / \ 2 3 / \ / \ 4 5 6 7 Recursive approach /\* Compute the "maxDepth" of a tree -- the number of nodes along the longest path from the root node down to the farthest leaf node. [Read More]
max  tree  kodeknight  binary-search-tree  BST 

Getting the size of Binary Search Tree

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

This problem demonstrates simple binary tree traversal. Given a binary tree, count the number of nodes in the tree.

Here is the code in c/cpp:

/\* Compute the number of nodes in a tree. \*/  
int size(struct node\* node) {   
    if (node==NULL) {   
        return(0);   
    } else {   
        return(size(node->left) + 1 + size(node->right));   
    }  
}
tree  kodeknight  size  recursion  binary-search-tree  BST 

Create Copy of a tree (cpp)

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

Given a binary tree,create the copy of the tree. node *copy(node* root)
node \*copy(node \*root)  
  
 node \*temp;  
   
 if(root==NULL)return(NULL);  
    
 temp = (node \*) malloc(sizeof(node));//or temp = newNode(root->data);  
 temp->value = root->value;  
  
 temp->left  = copy(root->left);  
 temp->right = copy(root->right);  
  
 return(temp);
tree  kodeknight  binary-search-tree  BST