i need help in the iteration code for a binary search tree. Solution /* Binary T

Question

i need help in the iteration code for a binary search tree.

Explanation / Answer

/* Binary Tree */ #include #include #include 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 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 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 data) lastData = node->data; else { cout right); } int maxDepth(struct Tree *node) { if(node == 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) return 0; int leftDepth = minDepth(node->left); int rightDepth = minDepth(node->right); return leftDepth 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; } Tree *lowestCommonAncestor(Tree *root, Tree *p, Tree *q) { Tree *left, *right; if(root == NULL) return NULL; if(root->left == p || root->left == q || root->right == p || root->right == q) return root; else { left = lowestCommonAncestor(root->left,p,q); right = lowestCommonAncestor(root->right, p,q); if(left && right) return root; 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) { static int lastData = INT_MIN; if(node == NULL) return; printTreeInOrder(node->left); cout left); printTreePostOrder(node->right); cout

Related Questions

Navigate

• Browse (All)
• Browse I
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.