A binary tree is made of nodes, where each node contains a left pointer, a right pointer, and a data element.
The root pointer points to the topmost node in the tree. The left and right pointers recursively point to smaller subtrees on either side. A null pointer represents a binary tree with no elements -- the empty tree.
The formal recursive definition is: a binary tree is either empty (represented by a null pointer), or is made of a single node, where the left and right pointers (recursive definition ahead) each point to a binary tree.
A binary search tree (BST) or ordered binary tree is a type of binary tree where the nodes are arranged in order: for each node, all elements in its left subtree are less-or-equal to the node (<=), and all the elements in its right subtree are greater than the node (>).
Basically, binary search trees are fast at insert and lookup. On average, a binary search tree algorithm can locate a node in an n node tree in order logn time (log base 2). Therefore, binary search trees are good for dictionary problems where the code inserts and looks up information indexed by some key. The logn behavior is the average case -- it's possible for a particular tree to be much slower depending on its shape.
The last tree out of major kinds of trees is a heap. A heap is a tree in which each node's children have values less than or equal to node's value. Consequently, the root node always has the largest value in the tree, which means that it's possible to find the maximum value in constant time: Simply return the root value. So, if extraction the max value needs to be fast, we should use a heap.
A leaf (external) node is a node that has no children while nonleaf node is also called internal node. The number of children of a node x in a tree T is the same as the degree of x. The length of the simple path from the root r to a node x is the depth of x in T. A level of a tree consists of all nodes at the same depth. The height of a node in a tree is the number of edges (hops) on the longest downward path from the node to a leaf, and the height of a tree is the height of its root. So, the height of a tree is equal to the largest depth of any node in the tree.
The height (depth) could be anywhere from ~log2n(best case, perfectly balanced) to ~n (worst case, a chain). Another thing to point out here is the importance of the height. We may appreciate the role of the height property of BST from the answer to the following question:
What's the worst-case running time of search(or insert) operation in a binary search tree containing n keys?
The following items are included in this Binary Search Tree example code.
It's based on the tree in the picture above.
SuccessorInOrder(x) if x.right != NULL; return minTree(x); y = x.p while x!= NULL && x == y.right x = y; y = x.p; return y;As described earlier, we broke the code into two cases. If the right subtree of node x is not empty, then the successor of x is just the leftmost node in x's right subtree. So, we just call minTree(x). However, if the right subtree of node x is empty, to find y, we simply go up the tree from x until we see a node that is the left child of its parent.
if x != NULL printTreeInOrder(x.left); print x.key; printTreeInOrder(x.right);Also called Inorder tree walk.
Level at 0: F Level at 1: B G Level at 2: A D I Level at 3: C E H
Here is the file for Binary Tree example below: BinaryTree.cpp.
/* Binary Tree */ #include <iostream> #include <deque> #include <climits> #include <vector> using namespace std; struct Tree { char data; Tree *left; Tree *right; Tree *parent; }; Tree* lookUp(struct Tree *node, char key) { if(node == NULL) return node; if(node->data == key) return node; else { if(node->data < key) return lookUp(node->right, key) ; else return lookUp(node->left, key); } } Tree* leftMost(struct Tree *node) { if(node == NULL) return NULL; while(node->left != NULL) node = node->left; return node; } struct Tree *newTreeNode(int data) { Tree *node = new Tree; node->data = data; node->left = NULL; node->right = NULL; node->parent = NULL; return node; } struct Tree* insertTreeNode(struct Tree *node, int data) { static Tree *p; Tree *retNode; //if(node != NULL) p = node; if(node == NULL) { retNode = newTreeNode(data); retNode->parent = p; return retNode; } if(data <= node->data ) { p = node; node->left = insertTreeNode(node->left,data); } else { p = node; node->right = insertTreeNode(node->right,data); } return node; } void isBST(struct Tree *node) { static int lastData = INT_MIN; if(node == NULL) return; isBST(node->left); /* check if the given tree is BST */ if(lastData < node->data) lastData = node->data; else { cout << "Not a BST" << endl; return; } isBST(node->right); return; } int treeSize(struct Tree *node) { if(node == NULL) return 0; else return treeSize(node->left) + 1 + treeSize(node->right); } int maxDepth(struct Tree *node) { if(node == NULL || (node->left == NULL && node->right == NULL)) return 0; int leftDepth = maxDepth(node->left); int rightDepth = maxDepth(node->right); return leftDepth > rightDepth ? leftDepth + 1 : rightDepth + 1; } int minDepth(struct Tree *node) { if(node == NULL || (node->left == NULL && node->right == NULL)) return 0; int leftDepth = minDepth(node->left); int rightDepth = minDepth(node->right); return leftDepth < rightDepth ? leftDepth + 1 : rightDepth + 1; } bool isBalanced(struct Tree *node) { if(maxDepth(node)-minDepth(node) <= 1) return true; else return false; } /* Tree Minimum */ Tree* minTree(struct Tree *node) { if(node == NULL) return NULL; while(node->left) node = node -> left; return node; } /* Tree Maximum */ Tree* maxTree(struct Tree *node) { while(node->right) node = node -> right; return node; } /* In Order Successor - a node which has the next higher key */ Tree *succesorInOrder(struct Tree *node) { /* if the node has right child, seccessor is Tree-Minimum */ if(node->right != NULL) return minTree(node->right); Tree *y = node->parent; while(y != NULL && node == y->right) { node = y; y = y->parent; } return y; } /* In Order Predecessor - a node which has the next lower key */ Tree *predecessorInOrder(struct Tree *node) { /* if the node has left child, predecessor is Tree-Maximum */ if(node->left != NULL) return maxTree(node->left); Tree *y = node->parent; /* if it does not have a left child, predecessor is its first left ancestor */ while(y != NULL && node == y->left) { node = y; y = y->parent; } return y; } void reverseOrderPrint(struct Tree *node) { if(node == NULL) return; if(node->left == NULL && node->right == NULL) { cout << node->data << " "; return; } reverseOrderPrint(node->right); cout << node->data << " "; reverseOrderPrint(node->left); } Tree *lowestCommonAncestor(Tree *node, Tree *p, Tree *q) { Tree *left, *right; if(node == NULL) return NULL; if(node->left == p || node->left == q || node->right == p || node->right == q) return node; left = lowestCommonAncestor(node->left,p,q); right = lowestCommonAncestor(node->right, p,q); if(left && right) return node; else return (left) ? left : right; } void clear(struct Tree *node) { if(node != NULL) { clear(node->left); clear(node->right); delete node; } } /* print tree in order */ /* 1. Traverse the left subtree. 2. Visit the root. 3. Traverse the right subtree. */ void printTreeInOrder(struct Tree *node) { if(node == NULL) return; printTreeInOrder(node->left); cout << node->data << " "; printTreeInOrder(node->right); } /* print tree in postorder*/ /* 1. Traverse the left subtree. 2. Traverse the right subtree. 3. Visit the root. */ void printTreePostOrder(struct Tree *node) { if(node == NULL) return; printTreePostOrder(node->left); printTreePostOrder(node->right); cout << node->data << " "; } /* print in preorder */ /* 1. Visit the root. 2. Traverse the left subtree. 3. Traverse the right subtree. */ void printTreePreOrder(struct Tree *node) { if(node == NULL) return; cout << node->data << " "; printTreePreOrder(node->left); printTreePreOrder(node->right); } /* In reverse of printTreeInOrder() */ void printTreeReverseOrder(struct Tree *node) { if(node == NULL) return; if(node->left == NULL && node->right == NULL) { cout << node->data << " "; return; } printTreeReverseOrder(node->right); cout << node->data << " "; printTreeReverseOrder(node->left); } /* recursion routine to find path */ void pathFinder(struct Tree *node, int path[], int level) { if(node == NULL) return; // save leaf node if(node->left == NULL && node->right == NULL) { path[level] = node->data; for(int i = 0; i <= level; i++) { cout << (char)path[i]; } cout << endl; return; } // save parent node path[level] = node->data; pathFinder(node->left, path, level+1); pathFinder(node->right, path, level+1); } bool matchTree(Tree *r1, Tree *r2) { /* Nothing left in the subtree */ if(r1 == NULL && r2 == NULL) return true; /* Big tree empty and subtree not found */ if(r1 == NULL || r2 == NULL) return false; /* Not matching */ if(r1->data != r2->data) return false; return (matchTree(r1->left, r2->left) && matchTree(r1->right, r2->right)); } bool subTree(Tree *r1, Tree *r2) { /*Big tree empty and subtree not found */ if(r1 == NULL) return false; if(r1->data == r2->data) if(matchTree(r1, r2)) return true; return (subTree(r1->left, r2) || subTree(r1->right, r2)); } bool isSubTree(Tree *r1, Tree *r2) { /* Empty tree is subtree */ if(r2 == NULL) return true; else return subTree(r1, r2); } /* change a tree so that the roles of the left and right hand pointers are swapped at every node */ void mirror(Tree *r) { if(r == NULL) return; Tree *tmp; mirror(r->left); mirror(r->right); /* swap pointers */ tmp = r->right; r->right = r->left; r->left = tmp; } /* create a new tree from a sorted array */ Tree *addToBST(char arr[], int start, int end) { if(end < start) return NULL; int mid = (start + end)/2; Tree *r = new Tree; r->data = arr[mid]; r->left = addToBST(arr, start, mid-1); r->right = addToBST(arr, mid+1, end); return r; } Tree *createMinimalBST(char arr[], int size) { return addToBST(arr,0,size-1); } /* Breadth first traversal using queue */ void BreadthFirstTraversal(Tree *root) { if (root == NULL) return; deque <Tree *> queue; queue.push_back(root); while (!queue.empty()) { Tree *p = queue.front(); cout << p->data << " "; queue.pop_front(); if (p->left != NULL) queue.push_back(p->left); if (p->right != NULL) queue.push_back(p->right); } cout << endl; } /* get the level of a node element: root level = 0 */ int getLevel(struct Tree *node, int elm, int level) { if(node == NULL) return 0; if(elm == node->data) return level; else if(elm < node->data) return getLevel(node->left, elm, level+1); else return getLevel(node->right, elm, level+1); } /* This code prints out all nodes at the same depth (level) */ void BreadthFirst_LevelElement_Print (struct Tree *root, vector<vector<int> > &v) { if(root == NULL) return; deque<Tree *> q; q.push_back(root); while(!q.empty()) { Tree *p = q.front(); int lev = getLevel(root, p->data, 0); v[lev].push_back(p->data); q.pop_front(); if(p->left) q.push_back(p->left); if(p->right)q.push_back(p->right); } return; } /* levelPrint() prints nodes at the same level This is simpler than the BreadthFirstTraversal(root) above It takes 2D vector with the same size of level (= MaxDepth+1) and fills elements as we traverse (preOrder) */ void levelPrint(struct Tree *node, vector<vector<char> >&elm, int level) { if(node == NULL) return; // leaf nodes if(node->left == NULL && node->right == NULL) { elm[level].push_back(node->data); return; } // other nodes elm[level++].push_back(node->data); levelPrint(node->left, elm, level); levelPrint(node->right, elm, level); } /* find n-th max node from a tree */ void NthMax(struct Tree* t) { static int n_th_max = 5; static int num = 0; if(t == NULL) return; NthMax(t->right); num++; if(num == n_th_max) cout << n_th_max << "-th maximum data is " << t->data << endl; NthMax(t->left); } /* Converting a BST into an Array */ void TreeToArray(struct Tree *node, int a[]){ static int pos = 0; if(node){ TreeToArray(node->left,a); a[pos++] = node->data; TreeToArray(node->right,a); } } /* Separate even/odd level elements */ /* This function is using BFS */ void level_even_odd(struct Tree *node) { vector<char> evenVec, oddVec; if (node == NULL) return; deque<struct Tree*> que; que.push_back(node); while(!que.empty()) { struct Tree *p = que.front(); int level = getLevel(node, p->data, 0) ; // even level if (level % 2 == 0) evenVec.push_back(p->data); else oddVec.push_back(p->data); que.pop_front(); if(p->left) que.push_back(p->left); if(p->right) que.push_back(p->right); } cout << "even level elements : "; for(int i = 0; i < evenVec.size(); i++) cout << evenVec[i] << " "; cout << endl << "odd level elements : "; for(int i = 0; i < oddVec.size(); i++) cout << oddVec[i] << " "; cout << endl; } int main(int argc, char **argv) { char ch, ch1, ch2; Tree *found; Tree *succ; Tree *pred; Tree *ancestor; char charArr[9] = {'A','B','C','D','E','F','G','H','I'}; Tree *root = newTreeNode('F'); insertTreeNode(root,'B'); insertTreeNode(root,'A'); insertTreeNode(root,'D'); insertTreeNode(root,'C'); insertTreeNode(root,'E'); insertTreeNode(root,'G'); insertTreeNode(root,'I'); insertTreeNode(root,'H'); /* is the tree BST? */ isBST(root); /* size of tree */ cout << "size = " << treeSize(root) << endl; /* max depth */ cout << "max depth = " << maxDepth(root) << endl; /* min depth */ cout << "min depth = " << minDepth(root) << endl; /* balanced tree? */ if(isBalanced(root)) cout << "This tree is balanced!\n"; else cout << "This tree is not balanced!\n"; /* min value of the tree*/ if(root) cout << "Min value = " << minTree(root)->data << endl; /* max value of the tree*/ if(root) cout << "Max value = " << maxTree(root)->data << endl; /* get the level of a data: root level = 0 */ cout << "Node B is at level: " << getLevel(root, 'B', 0) << endl; cout << "Node H is at level: " << getLevel(root, 'H', 0) << endl; cout << "Node F is at level: " << getLevel(root, 'F', 0) << endl; /* separate even/odd level elements */ level_even_odd(root); ch = 'B'; found = lookUp(root,ch); if(found) { cout << "Min value of subtree " << ch << " as a root is " << minTree(found)->data << endl; cout << "Max value of subtree " << ch << " as a root is " << maxTree(found)->data << endl; } ch = 'B'; found = lookUp(root,ch); if(found) { succ = succesorInOrder(found); if(succ) cout << "In Order Successor of " << ch << " is " << succesorInOrder(found)->data << endl; else cout << "In Order Successor of " << ch << " is None\n"; } ch = 'E'; found = lookUp(root,ch); if(found) { succ = succesorInOrder(found); if(succ) cout << "In Order Successor of " << ch << " is " << succesorInOrder(found)->data << endl; else cout << "In Order Successor of " << ch << " is None\n"; } ch = 'I'; found = lookUp(root,ch); if(found) { succ = succesorInOrder(found); if(succ) cout << "In Order Successor of " << ch << " is " << succesorInOrder(found)->data << endl; else cout << "In Order Successor of " << ch << " is None\n"; } ch = 'B'; found = lookUp(root,ch); if(found) { pred = predecessorInOrder(found); if(pred) cout << "In Order Predecessor of " << ch << " is " << predecessorInOrder(found)->data << endl; else cout << "In Order Predecessor of " << ch << " is None\n"; } ch = 'E'; found = lookUp(root,ch); if(found) { pred = predecessorInOrder(found); if(pred) cout << "In Order Predecessor of " << ch << " is " << predecessorInOrder(found)->data << endl; else cout << "In Order Predecessor of " << ch << " is None\n"; } ch = 'I'; found = lookUp(root,ch); if(found) { pred = predecessorInOrder(found); if(pred) cout << "In Order Predecessor of " << ch << " is " << predecessorInOrder(found)->data << endl; else cout << "In Order Predecessor of " << ch << " is None\n"; } /* Lowest Common Ancestor */ ch1 = 'A'; ch2 = 'C'; ancestor = lowestCommonAncestor(root, lookUp(root,ch1), lookUp(root,ch2)); if(ancestor) cout << "The lowest common ancestor of " << ch1 << " and " << ch2 << " is " << ancestor->data << endl; ch1 = 'E'; ch2 = 'H'; ancestor = lowestCommonAncestor(root, lookUp(root,ch1), lookUp(root,ch2)); if(ancestor) cout << "The lowest common ancestor of " << ch1 << " and " << ch2 << " is " << ancestor->data << endl; ch1 = 'D'; ch2 = 'E'; ancestor = lowestCommonAncestor(root, lookUp(root,ch1), lookUp(root,ch2)); if(ancestor) cout << "The lowest common ancestor of " << ch1 << " and " << ch2 << " is " << ancestor->data << endl; ch1 = 'G'; ch2 = 'I'; ancestor = lowestCommonAncestor(root, lookUp(root,ch1), lookUp(root,ch2)); if(ancestor) cout << "The lowest common ancestor of " << ch1 << " and " << ch2 << " is " << ancestor->data << endl; ch1 = 'H'; ch2 = 'I'; ancestor = lowestCommonAncestor(root, lookUp(root,ch1), lookUp(root,ch2)); if(ancestor) cout << "The lowest common ancestor of " << ch1 << " and " << ch2 << " is " << ancestor->data << endl; /* print tree in order */ cout << "increasing sort order\n"; printTreeInOrder(root); cout << endl; /* print tree in postorder*/ cout << "post order \n"; printTreePostOrder(root); cout << endl; /* print tree in preorder*/ cout << "pre order \n"; printTreePreOrder(root); cout << endl; /* print tree in reverse order*/ cout << "reverse order \n"; printTreeReverseOrder(root); cout << endl; /* lookUp */ ch = 'D'; found = lookUp(root,ch); if(found) cout << found->data << " is in the tree\n"; else cout << ch << " is not in the tree\n"; /* lookUp */ ch = 'M'; found = lookUp(root,ch); if(found) cout << found->data << " is in the tree\n"; else cout << ch << " is not in the tree\n"; /* printing all paths : Given a binary tree, print out all of its root-to-leaf paths, one per line. Uses a recursive helper to do the work. */ cout << "printing paths ..." << endl; int path[10]; pathFinder(root, path, 0); /* find n-th maximum node */ NthMax(root); /* Traversing level-order. We visit every node on a level before going to a lower level. This is also called Breadth-first traversal.*/ cout << "printing with Breadth-first traversal" << endl; BreadthFirstTraversal(root); /* Prints all element at the same depth (level) */ int row = maxDepth(root); vector<vector<int> > levVec(row+1); BreadthFirst_LevelElement_Print(root, levVec); for(int m = 0; m < levVec.size(); m++) { cout << "Level at " << m << ": "; for(int n = 0; n < levVec[m].size(); n++) cout << (char)levVec[m][n] << " "; cout << endl; } /* levelPrint() prints nodes at the same level This is simpler than the BreadthFirstTraversal(root) above It takes 2D vector (elm) with the same size of level (= MaxDepth+1) and fills elements as we traverse (preOrder) */ vector<vector<char> > elm; int mxDepth = maxDepth(root); elm.resize(mxDepth+1); int level = 0; levelPrint(root, elm, level); cout << "levelPrint() " << endl; for(int i = 0; i <= mxDepth; i++) { cout << "level " << i << ": " ; for(int j = 0; j < elm[i].size(); j++) cout << elm[i][j] << " "; cout << endl; } /* convert the tree into an array */ int treeSz = treeSize(root); int *array = new int[treeSz]; TreeToArray(root,array); cout << "New array: "; for (int i = 0; i < treeSz; i++) cout << (char)array[i] << ' '; cout << endl; delete [] array; /* subtree */ Tree *root2 = newTreeNode('D'); insertTreeNode(root2,'C'); insertTreeNode(root2,'E'); cout << "1-2 subtree: " << isSubTree(root, root2) << endl; Tree *root3 = newTreeNode('B'); insertTreeNode(root3,'A'); insertTreeNode(root3,'D'); insertTreeNode(root3,'C'); insertTreeNode(root3,'E'); cout << "1-3 subtree: " << isSubTree(root, root3) << endl; Tree *root4 = newTreeNode('B'); insertTreeNode(root4,'D'); insertTreeNode(root4,'C'); insertTreeNode(root4,'E'); cout << "1-4 subtree: " << isSubTree(root, root4) << endl; cout << "2-3 subtree: " << isSubTree(root2, root3) << endl; cout << "3-2 subtree: " << isSubTree(root3, root2) << endl; /* swap left and right */ mirror(root); /* deleting a tree */ clear(root); /* make a new tree with minimal depth */ Tree *newRoot = createMinimalBST(charArr,9); return 0; }
From the run, we get:
size = 9 max depth = 3 min depth = 2 This tree is balanced! Min value = A Max value = I Node B is at level: 1 Node H is at level: 3 Node F is at level: 0 even level elements : F A D I odd level elements : B G C E H Min value of subtree B as a root is A Max value of subtree B as a root is E In Order Successor of B is C In Order Successor of E is F In Order Successor of I is None In Order Predecessor of B is A In Order Predecessor of E is D In Order Predecessor of I is H The lowest common ancestor of A and C is B The lowest common ancestor of E and H is F The lowest common ancestor of D and E is B The lowest common ancestor of G and I is F The lowest common ancestor of H and I is G increasing sort order A B C D E F G H I post order A C E D B H I G F pre order F B A D C E G I H reverse order I H G F E D C B A D is in the tree M is not in the tree printing paths ... FBA FBDC FBDE FGIH 5-th maximum data is E printing with Breadth-first traversal F B G A D I C E H Level at 0: F Level at 1: B G Level at 2: A D I Level at 3: C E H levelPrint() level 0: F level 1: B G level 2: A D I level 3: C E H New array: A B C D E F G H I New array: A B C D E F G H I 1-2 subtree: 1 1-3 subtree: 1 1-4 subtree: 0 2-3 subtree: 0 3-2 subtree: 1
The following example shows binary serach algorithms using iterative and recursive.
We look for an element x in a sorted array. It compares xx or the array range equals to zero.
#include <iostream> using namespace std; // iterative int bsearch(int a[], int sz, int x) { int low = 0; int high = sz -1; while(low <= high) { int mid = (low+high)/2; if(x < a[mid]) high = mid - 1; else if(x > a[mid]) low = mid + 1; else return a[mid]; } return -1; } // recursive int bsearch_recursive(int a[], int low, int high, int x) { if(low > high) return -1; int mid = (low + high)/2; if(x < a[mid]) bsearch_recursive(a, low, mid-1, x); else if(x > a[mid]) bsearch_recursive(a, mid+1, high, x); else return a[mid]; } void print(int n) { if(n == -1) { cout << "not found" << endl; return; } cout << "found" << endl; } int main() { int a[]={3, 7, 9, 16, 23, 34, 67, 87, 92}; int arraySize = sizeof(a)/sizeof(int); int result; result = bsearch(a, arraySize, 7); print(result); result = bsearch(a, arraySize, 92); print(result); result = bsearch(a, arraySize, 77); print(result); result = bsearch_recursive(a, 0, arraySize-1, 7); print(result); result = bsearch_recursive(a, 0, arraySize-1, 92); print(result); result = bsearch_recursive(a, 0, arraySize-1, 77); print(result); return 0; }
Output:
found found not found found found not found
/* 3 / \ -1 2 / \ / 5 7 1 */ #include <iostream> using namespace std; typedef struct Tree { int data; Tree *left; Tree *right; } Node; /* recursion routine to find path */ void pathFinder(Node* node, int path[], int level) { if(node == NULL) return; // leaf node save if(node->left == NULL && node->right == NULL) { path[level] = node->data; int sum = 0; for(int i = 0; i <= level; i++) { cout << path[i] << " "; sum += path[i]; } cout << " sum = " << sum << endl; return; } // parent node save path[level] = node->data; pathFinder(node->left, path, level+1); pathFinder(node->right, path, level+1); } struct Tree* insertNode(Tree *node, int data) { node->data = data; node->left = NULL; node->right = NULL; return node; } int main(int argc, char **argv) { Tree *root = NULL; Tree *nodeLeft = NULL; Tree *nodeRight = NULL; // unsorted binary tree // root root = insertNode(new Tree, 3); // 1st level nodeLeft = insertNode(new Tree, -1); root->left = nodeLeft; nodeRight = insertNode(new Tree, 2); root->right = nodeRight; // 2nd level nodeLeft->left = insertNode(new Tree, 5); nodeLeft->right = insertNode(new Tree, 7); nodeRight->left = insertNode(new Tree, 1); // path find int path[10]; pathFinder(root,path,0); return 0; } /* output */ /* 3 -1 5 sum = 7 3 -1 7 sum = 9 3 2 1 sum = 6 */
The code below constructs binary search tree with minimal height for an int array which is already sorted in increasing order.
The middle element becomes a root and each sides of the mid element go to either left or right side of the tree. We do it recursively so that middle element always becomes the root for each subtree.
#include <iostream> typedef struct node { node *left; node *right; int data; } Node; Node *btree(int a[], int low, int high) { if(low > high) return NULL; int mid = (low + high) /2; Node *nd = new Node; nd->data = a[mid]; nd->left = btree(a, low, mid-1); nd->right = btree(a, mid+1, high); return nd; } int main() { int a[] = {1,2,3,4,5,6,7,8,9,10,11,12,13,14,15}; int size = sizeof(a)/sizeof(int); Node *root = btree(a, 0, size-1); return 0; }
Is the two BST same?
The code below compares both structure and data and check if both are the same.
bool isTreeEqual (TREE*, TREE*) takes both of the nodes as its parameters. As soon as it detects the difference, it returns false, and returns true only after passing all the tests.
/* Compare two Binary Trees */ #include <iostream> using namespace std; typedef struct Tree { char data; Tree *left; Tree *right; } TREE; TREE* newTree(char ch) { TREE *node = new TREE; node->data = ch; node->left = NULL; node->right = NULL; return node; } void insertTreeNode(TREE *node, char ch) { TREE *newNode = new TREE; newNode->data = ch; newNode->left = NULL; newNode->right = NULL; while(node) { if(ch <= node->data) { if(node->left == NULL) { node->left = newNode; return; } else node = node->left; } else { if(node->right == NULL) { node->right = newNode; return; } else node = node->right; } } } bool isTreeEqual(TREE* node1, TREE* node2) { // handles the roots are equal or both NULL if(node1 == node2) return true; // one of them NULL if(node1 == NULL || node2 == NULL) return false; // data check if(node1->data != node2->data) return false; if(!isTreeEqual(node1->left, node2->left)) return false; if(!isTreeEqual(node1->right, node2->right)) return false; // everything has been checked, return true return true; } void clear(TREE* node) { if(node != NULL) { clear(node->left); clear(node->right); delete node; } } int main(int argc, char **argv) { char charArr[] = {'F','B','A','D','C','E','G','I','H'}; int size = sizeof(charArr)/sizeof(charArr[0]); TREE *root1 = newTree('F'); for(int i = 1; i < size; i++) insertTreeNode(root1,charArr[i]); // same roots cout << "isTreeEqual(root1, root1) = " << isTreeEqual(root1, root1) << endl; TREE *root2 = newTree('F'); for(int i = 1; i < size; i++) insertTreeNode(root2,charArr[i]); // same structure & data cout << "isTreeEqual(root1, root2) = " << isTreeEqual(root1, root2) << endl; // same structure but the last leaf is different char charArr3[] = {'F','B','A','D','C','E','G','I','Z'}; TREE *root3 = newTree('F'); for(int i = 1; i < size; i++) insertTreeNode(root3,charArr3[i]); cout << "isTreeEqual(root1, root3) = " << isTreeEqual(root1, root3) << endl; // root4 has one more leaf node 'J' char charArr4[] = {'F','B','A','D','C','E','G','I','H','J'}; size = sizeof(charArr4)/sizeof(charArr4[0]); TREE *root4 = newTree('F'); for(int i = 1; i < size; i++) insertTreeNode(root4,charArr4[i]); cout << "isTreeEqual(root1, root4) = " << isTreeEqual(root1, root4) << endl; // root = NULL cout << "isTreeEqual(root1, 0) = " << isTreeEqual(root1, 0) << endl; // both roots are NULL cout << "isTreeEqual(0, 0) = " << isTreeEqual(0, 0) << endl; // deallocate clear(root1); clear(root2); clear(root3); clear(root4); return 0; }
Output:
isTreeEqual(root1, root1) = 1 isTreeEqual(root1, root2) = 1 isTreeEqual(root1, root3) = 0 isTreeEqual(root1, root4) = 0 isTreeEqual(root1, 0) = 0 isTreeEqual(0, 0) = 1
Deleting a key from a binary search is a little bit tricky. We can categorize it in three groups depending its operations:
The colde below is based on the BST in the picture.
/* Binary Tree - deleting a node*/ #include <iostream> using namespace std; typedef struct Tree { char data; Tree *left; Tree *right; Tree *parent; } TREE; TREE *newTreeNode(int data) { TREE *node = new TREE; node->data = data; node->left = NULL; node->right = NULL; node->parent = NULL; return node; } void insertTreeNode(TREE *node, char ch) { TREE *newNode = new TREE; newNode->data = ch; newNode->left = NULL; newNode->right = NULL; while(node) { if(ch <= node->data) { if(node->left == NULL) { newNode->parent = node; node->left = newNode; return; } else node = node->left; } else { if(node->right == NULL) { newNode->parent = node; node->right = newNode; return; } else node = node->right; } } } TREE *getNode(TREE *node, char c) { if(node == NULL) return node; if(c < node->data) return getNode(node->left,c); else if( c > node->data) return getNode(node->right, c); else return node; } char treeMax(TREE *node) { while(node->right) { node = node->right; } return node->data; } void printTreeInOrder(TREE *node) { if(node == NULL) return; printTreeInOrder(node->left); cout << node->data << " "; printTreeInOrder(node->right); } char predecessorInOrder(TREE *node) { if(node->left) return treeMax(node->left); TREE *y = node->parent; while(node == y->left) { node = y; y = y->parent; } return y->data; } void deleteKey(TREE *root, char ch) { TREE *node, *p, *child, *pred; // get the node for the key node = getNode(root, ch); // leaf node - just delete the node if(node->left == NULL && node->right == NULL) { if(node->parent) p = node->parent; if(node == p->left) p->left = NULL; else p->right = NULL; delete node; return; } // two children - replace it with its predecessor and delete if(node->left && node->right) { char ch_pred = predecessorInOrder(node); pred = getNode(root, ch_pred); if(pred->parent->left == pred) pred->parent->left = NULL; else if(pred->parent->right == pred) pred->parent->right = NULL; node->data = pred->data; delete pred; return; } // only one child // replace it with its child and delete if(node->left) child = node->left; else if(node->right) child = node->right; p = node->parent; if(p->left && p->left == node) { p->left = child; } else if (p->right && p->right == node) { p->right = child; } child->parent = p; delete node; return; } int main(int argc, char **argv) { TREE *root = newTreeNode('F'); insertTreeNode(root,'B'); insertTreeNode(root,'A'); insertTreeNode(root,'D'); insertTreeNode(root,'C'); insertTreeNode(root,'E'); insertTreeNode(root,'G'); insertTreeNode(root,'I'); insertTreeNode(root,'H'); printTreeInOrder(root); cout << "\ndeleteKey(root, 'A')" << endl; deleteKey(root, 'A'); printTreeInOrder(root); cout << "\ninsertTreeNode(root,'A')" << endl; insertTreeNode(root,'A'); printTreeInOrder(root); cout << "\ndeleteKey(root, 'I')" << endl; deleteKey(root, 'I'); cout << "deleteKey(root, 'H')" << endl; deleteKey(root, 'H'); printTreeInOrder(root); cout << "\ninsertTreeNode(root,'I')" << endl; insertTreeNode(root,'I'); cout << "insertTreeNode(root,'H')" << endl; insertTreeNode(root,'H'); printTreeInOrder(root); cout << "\ndeleteKey(root, 'F') " << endl; deleteKey(root, 'F'); printTreeInOrder(root); return 0; }
Output is:
A B C D E F G H I deleteKey(root, 'A') B C D E F G H I insertTreeNode(root,'A') A B C D E F G H I deleteKey(root, 'I') deleteKey(root, 'H') A B C D E F G insertTreeNode(root,'I') insertTreeNode(root,'H') A B C D E F G H I deleteKey(root, 'F') A B C D E G H I
No algorithm that sort by comparison based can do beter than nlogn performance in the average or worst case.
Given n items, there are n! permutations of these elements. Each internal node of binary decision tree represents a comparison ai≤aj and the leaves of the tree represents on of n!. Though there are numerous constructs for binary decision tree, we can compute its minimum height, h. In other words, there must be some leaf that requires h comparison nodes in the tree from the root to that leaf.
Let's assume we have complete binary tree of height h in which all non-leaf nodes have both a left and a right child. This tree contains n=2h−1 nodes. The height will be h=log(n+1). Any binary decision tree with n! leaf nodes has at least n! nodes. So, we need to compute h=[log(n!)] to determine the height of the binary decision tree.
h≥log(n!)=log(n(n−1)(n−2)...(2)(1))=log(n)+log(n−1)+log(n−2)+...+log2+log1=n∑i=n/2logi+n/2−1∑i=1logi≥n∑i=n/2logi≥n∑i=n/2logn2=n2logn2=Ω(nlogn)
So, any sorting algorithm using comparisons will require Ω(nlogn) comparisons to sort.
An alternative sorting algorithm such as bucket sort would perform better under specific conditions. That's because it is not solely rely on comparing elements.