IsBST : Check whether the tree provided is BST or not
Posted on May 11, 2011
(Last modified on August 7, 2020)
| 6 minutes
| Kinshuk Chandra
Problem
This background is used by the next two problems: Given a plain binary tree, examine the tree to determine if it meets the requirement to be a binary search tree. To be a binary search tree, for every node, all of the nodes in its left tree must be <= the node, and all of the nodes in its right subtree must be > the node. Consider the following four examples…
[Read More]Count binary search trees–Given N nodes, how many structurally BST are possible?
Posted on May 11, 2011
(Last modified on August 7, 2020)
| 2 minutes
| Kinshuk Chandra
Problem:
This is not a binary tree programming problem in the ordinary sense – it’s more of a math/combinatorics recursion problem that happens to use binary trees. Suppose you are building an N node binary search tree with the values 1..N. How many structurally different binary search trees are there that store those values?
Solution
Total number of possible Binary Search Trees with n different keys = Catalan number Cn = (2n)!
[Read More]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]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]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]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]Print binary search tree in increasing order
Posted on May 11, 2011
(Last modified on August 7, 2020)
| 1 minutes
| Kinshuk Chandra
Very good information indeed. Thanks for posting t…
CPP Tutorials - Jan 1, 2015
Very good information indeed. Thanks for posting this here. You can find more information on Binary search tree (BST) here in the following link with examples.
Binary search tree (BST) in Cpp with examples
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]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]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]