[greeksforgreeks] A program to check if a binary tree is BST or not.
The following are the best solution greeksforgreeks provided.
Solution 1:
Using in order traversal, and store the result in a auxiliary three element array, if the array is sorted in ascending order, the tree is BST.
or we can optimization the space like:
or we can optimization the space like:
[code]
bool isBST(Node *root)
{
static struct Node *prev = NULL;
if (root)
{
if(!isBST(root->left))
return false;
if ( prev != NULL && root->value <= prev->value)
return false;
prev = root;
return isBST(root->right);
}
return true;
}
Find lowest common ancestor of two nodes in a binary tree.
Solution:
Need to implement a helper function which find if a node is a child of the root node.
[code]
bool Has(Node *r, Node *p)
{
if (r == NULL) return false;
if (r == p) return true;
return Has(r->left, p) || Has(r->right, p);
}
Node *LCA(Node *r, Node *p, Node *q)
{
if (Has(r->left, p) && Has(r->left, q))
return LCA(r->left, p, q);
if (Has(r->right, p) && Has(r->right, q))
return LCA(r-right, p, q);
return r;
}
Find level of a node in a binary tree.
Solution:
[code]
int findLevel(Node *r, Node *p, int level)
{
if (root == NULL)
return -1;
if ( root == p ) return level;
int ll = findLevel(root->left, p, level+1);
if (ll != -1) return ll;
return findLevel(root->right, p, level+1);
}
Find Distance between two nodes in a binary tree.
Solution:
formula: Dist(p,q) = Dist(r,p) + Dist(r,q) - 2*Dist(r, lca)
formula: Dist(p,q) = Dist(r,p) + Dist(r,q) - 2*Dist(r, lca)
[Code]
int Distance(Node *r, Node *p, Node *q)
{
Node *lc = LCA(r, p, q);
int Distrp = findLevel(r, p, 0);
int Distrq = findLevel(r, q, 0);
int Distlca = findLevel(r, lc, 0);
return Dist(r, p) + Dist(r, q) - 2* Dist(r, lc);
}
Binary tree iterative pre-order traversal.
Solution:
using a auxiliary stack
[Code]
void Preorder(Node *r)
{
stack<Node*>s;
Node *c;
s.push(r);
while(!s.empty()) {
Node *t = s.top();
// print out the value of the Node
cout << t->value << endl;
s.pop();
if(t->right) s.push(t->right);
if(t->left) s.push(t->left);
}
}
Binary tree iterative post-order traversal.
Solution:
using two auxiliary stacks
using two auxiliary stacks
[Code]
void Postorder(Node *r)
{
Node *c;
stack<Node*>s;
stack<Node*>output;
s.push(r);
while(!s.empty()) {
Node *t = s.top();
output.push(t);
s.pop();
if(t->left) s.push(t->left);
if(t->right) s.push(t->right);
}
while(!output.empty()) {
cout << output.top()->value << endl;
output.pop();
}
}
Binary tree iterative in-order traversal.
Solution:
using one auxiliary stack.
[code]
void Inorder(Node *r)
{
Node *c = r;
stack<Node *> s;
while(1) {
if(c) {
s.push(c);
c = c->left;
}
else{
if (s.empty()) break;
c = s.top();
cout << c->value << endl;
s.pop();
c = c->right;
}
}
}
Traverse a binary tree level by level.
Solution:
1. find the max height of the tree;
2. print the tree level indexed by the level index;
[code]
int TreeHeight( Node *r)
{
if (r == NULL) return 0;
return max(TreeHeight(r->left), TreeHeight(r->right)) + 1;
}
void printLevel(Node *r, int level)
{
if (r==NULL) return;
if ( level <0 ) return;
if (level == 0)
cout << r->value <<endl;
printLevel(r->left, level - 1);
printLevel(r->right, level - 1);
}
Find number of leaves in a binary tree.
Solution1:
[code]
int findLeaves(Node *r)
{
if (r == NULL) return 0;
if (r -> left == NULL && r->right == NULL) return 1;
return findLeaves(r->left) + findLeaves(r->right);
}
Solution2: using static variable
[code]
int findLeaves(Node *r)
{
static int count = 0;
if (r == NULL) return count;
if (r -> left == NULL && r->right == NULL) count ++;
return findLeaves(r->left) + findLeaves(r->right);
}
Clone a binary tree
Solution: using recursive method;
[code]
struct Node {
int value;
Node *left;
Node *right;
};
Node *cloneBinaryTree(Node *r)
{
if (r==NULL) return NULL;
Node *p = new Node;
p->value = r->value;
p->left = cloneBinaryTree(r->left);
p->right = cloneBinaryTree(r->right);
return p;
}
using one auxiliary stack.
[code]
void Inorder(Node *r)
{
Node *c = r;
stack<Node *> s;
while(1) {
if(c) {
s.push(c);
c = c->left;
}
else{
if (s.empty()) break;
c = s.top();
cout << c->value << endl;
s.pop();
c = c->right;
}
}
}
Traverse a binary tree level by level.
Solution:
1. find the max height of the tree;
2. print the tree level indexed by the level index;
[code]
int TreeHeight( Node *r)
{
if (r == NULL) return 0;
return max(TreeHeight(r->left), TreeHeight(r->right)) + 1;
}
void printLevel(Node *r, int level)
{
if (r==NULL) return;
if ( level <0 ) return;
if (level == 0)
cout << r->value <<endl;
printLevel(r->left, level - 1);
printLevel(r->right, level - 1);
}
Find number of leaves in a binary tree.
Solution1:
[code]
int findLeaves(Node *r)
{
if (r == NULL) return 0;
if (r -> left == NULL && r->right == NULL) return 1;
return findLeaves(r->left) + findLeaves(r->right);
}
Solution2: using static variable
[code]
int findLeaves(Node *r)
{
static int count = 0;
if (r == NULL) return count;
if (r -> left == NULL && r->right == NULL) count ++;
return findLeaves(r->left) + findLeaves(r->right);
}
Clone a binary tree
Solution: using recursive method;
[code]
struct Node {
int value;
Node *left;
Node *right;
};
Node *cloneBinaryTree(Node *r)
{
if (r==NULL) return NULL;
Node *p = new Node;
p->value = r->value;
p->left = cloneBinaryTree(r->left);
p->right = cloneBinaryTree(r->right);
return p;
}
