Duplicate removal in Binary Search Tree
Posted on September 26, 2011
(Last modified on August 7, 2020)
| 2 minutes
| Kinshuk Chandra
#include <stdio.h\> class BinarySearchTree { private: int data; BinarySearchTree \*left, \*right; public: BinarySearchTree(const int d):data(d), left(NULL), right(NULL){} ~BinarySearchTree() { if(left !\= NULL) { delete left; } if(right !\= NULL) { delete right; } } //remove duplicates void removeDup() { if(left) { left\-\>removeDup(); left\-\>remove(data, this); } if(right) right\-\>removeDup(); } void remove(int value, BinarySearchTree \*parent) { if(value < data && left) { left\-\>remove(value, this); } else if(value \> data && right) { right\-\>remove(value, this); } else remove(parent); } void remove(BinarySearchTree \*parent) //remove this node { if(left \=\= NULL && right \=\= NULL) //leaf { ((parent\-\>left \=\= this) ?
[Read More]Find nth largest value in a BST
Posted on September 11, 2011
(Last modified on August 7, 2020)
| 1 minutes
| Kinshuk Chandra
Hi there I was just going through your this post a… bakwasscoder - Jun 5, 2012Hi there
I was just going through your this post and had a small doubt.
Shouldn’t we do a stack based iterative traversal to get the correct value in this code ? This recursive may give wrong result as it will start counting after the rightmost element has been found. This element won’t be the nth largest in BST.
[Read More]Find nth largest value in a BST
Posted on September 11, 2011
(Last modified on August 7, 2020)
| 1 minutes
| Kinshuk Chandra
Simplest solution is to do a reverse in order search and maintain a global counter.
ReverseInOrder(Tree T, n)
1. if (T->right != null ) ReverseInOrder(T->right)
2. if (count==n) return T. Else count++
3. if (T->left != null ) ReverseInOrder(T->left)
What is BST or Binary Search tree?
Posted on May 16, 2011
(Last modified on August 7, 2020)
| 6 minutes
| Kinshuk Chandra
A binary search tree (BST) is a tree which has following property :
Every node’s left sub-tree has a key less than the node’s key, and every right sub-tree has a key greater than the node’s key.
The major advantage of binary search trees is that the related sorting algorithms and search algorithms, such as in-order traversal, can be very efficient. This data structure is perfect for advanced interview questions. See the figure below for this tree:
[Read More]Interview Questions on Binary Search tree
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. Given a binary tree, count the number of nodes in the tree. Given a binary tree, find the maximum depth the number of nodes along the longest path from the root node down to the farthest leaf node. Write a code to find the minimum and maximum value in binary search tree Print the BST in increasing order…to put this in different way, it simply means to print in inorder traversal Print the post order traversal (recursive) Print the paths in binary search tree from root to leaves.
[Read More]BST : Improving search by using sentinel
Posted on May 11, 2011
(Last modified on August 7, 2020)
| 2 minutes
| Kinshuk Chandra
A normal search across a BST (Binary Search Tree) would look like this
bool BinaryTree::Search (int data ) { Node \*current = this\->root; while ( current != NULL ) { if (current->data < data) { current = current->left; } else if (current->data > data) { current = current->right; } else if ( current->data == data ) { return true; } } return false; } You keep going down the tree, until you find a node whose value is equal to one you are looking for, or you bail out when you hit a leaf (NULL) node.
[Read More]Nth node in inorder traversal
Posted on May 11, 2011
(Last modified on August 7, 2020)
| 1 minutes
| Kinshuk Chandra
Problem
Here we have to return pointer to nth node in the inorder traversal
Solution
// Get the pointer to the nth inorder node in "nthnode" void nthinorder(node \*root, int n, mynode \*\*nthnode) { static whichnode; static found; if(!found) { if(root) { nthinorder(root->left, n , nthnode); if(++whichnode == n) { printf("\\nFound %dth node\\n", n); found = 1; \*nthnode = root; // Store the pointer to the nth node. } nthinorder(root->right, n , nthnode); } } } 17\.
[Read More]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]