Tree algo Flashcards

Question

Check if subtree is present in a tree Given two binary trees with head reference as T and S having at most N nodes. The task is to check if S is present as subtree in T. A subtree of a tree T1 is a tree T2 consisting of a node in T1 and all of its descendants in T1. Example 1: ``` Input: T: 1 S: 3 / \ / 2 3 4 / \ / N N 4 Output: 1 Explanation: S is present in T ``` Example 2: ``` Input: T: 26 S: 26 / \ / \ 10 N 10 N / \ / \ 20 30 20 30 / \ / \ 40 60 40 60 Output: 1 Explanation: S and T are both same. Hence, it can be said that S is a subtree of T. Your Task: You don't need to read input or print anything. Your task is to complete the function isSubtree() that takes root node of S and T as parameters and returns 1 if S is a subtree of T else 0. ``` Expected Time Complexity: O(N). Expected Auxiliary Space: O(N).

Answer 1

Algorithm: Find inorder and preorder traversals of T, store them in two lists. Find inorder and preorder traversals of S, store them in two lists. If inorder and preorder lists of T occurs in inorder and preorder lists of S then return true else false. ``` class Solution { vector(Node*> nodes; public: bool isSubTree(Node* S, Node* T) { if (!S && !T) return true; if (!S || !T) return false; getDepth(S, getDepth(T, -1)); for (Node* n: nodes) if (identical(n, T)) return true; return false; } int getDepth(Node* r, int d) { if (!r) return -1; int depth = max(getDepth(r->left, d), getDepth(r->right, d)) + 1; // Check if depth equals required value // Require depth is -1 for tree t (only return the depth, no push) if (depth == d) nodes.push_back(r); return depth; } bool identical(Node* a, Node* b) { if (!a && !b) return true; if (!a || !b || a->data != b->data) return false; return identical(a->left, b->left) && identical(a->right, b->right); } }; ``` another approach One simple approach is to check if the node data is same and then check for subtree from that node. Do this recursively for left and right subtree. ``` class Solution { public: ``` ``` bool isSame(Node *a,Node*b) // to check if both the subtrees are same { if(a==NULL && b==NULL) //base case return true; if(a==NULL||b==NULL) // base case return false; if(a->data!=b->data) // base case return false; return isSame(a->left,b->left) && isSame(a->right,b->right); // recurcive call to check for left and right subtrees } ``` ``` bool isSubTree(Node* T, Node* S) { // Your code here if(T==NULL && S==NULL) // base case return true; if(T==NULL) // base case return false; if(T->data==S->data&&isSame(T,S)) // if any node's data is found same check for same subtree return true; return isSubTree(T->left,S)||isSubTree(T->right,S); // recursively check for left and right subtree ``` } };

Answer 2

Algorithm: Traverse the tree in inorder fashion. While visiting each node, keep track of DLL’s head and tail pointers, insert each visited node to the end of DLL using tail pointer. Return head of the list. Below is the implementation of the above approach: ``` // A C++ program for in-place // conversion of Binary Tree to DLL #include (bits/stdc++.h> using namespace std; ``` ``` /* A binary tree node has data, and left and right pointers */ class node { public: int data; node* left; node* right; }; ``` ``` /* This is the core function to convert Tree to list.*/ void bintree2listUtil(node* root, node** head, node** tail) { if (root == NULL) return; ``` bintree2listUtil(root->left, head, tail); if (*head == NULL) { *head = root; } root->left = *tail; if (*tail != NULL) { (*tail)->right = root; } *tail = root; bintree2listUtil(root->right, head, tail); } ``` // The main function that first calls // bintree2listUtil() node* bintree2list(node* root) { // Base case if (root == NULL) return root; ``` node* head = NULL; node* tail = NULL; bintree2listUtil(root, &head, &tail); return head; } ``` /* Helper function that allocates a new node with the given data and NULL left and right pointers. */ node* newNode(int data) { node* new_node = new node(); new_node->data = data; new_node->left = new_node->right = NULL; return (new_node); } ``` ``` /* Function to print nodes in a given doubly linked list */ void printList(node* node) { while (node != NULL) { cout (( node->data (( " "; node = node->right; } } ``` ``` /* Driver code*/ int main() { // Let us create the tree shown in above diagram node* root = newNode(10); root->left = newNode(12); root->right = newNode(15); root->left->left = newNode(25); root->left->right = newNode(30); root->right->left = newNode(36); ``` ``` // Convert to DLL node* head = bintree2list(root); ``` ``` // Print the converted list printList(head); ``` return 0; }

Answer 3

The idea can be described using the below steps. 1) Write a general-purpose function that concatenates two given circular doubly lists (This function is explained below). 2) Now traverse the given tree ….a) Recursively convert left subtree to a circular DLL. Let the converted list be leftList. ….a) Recursively convert right subtree to a circular DLL. Let the converted list be rightList. ….c) Make a circular linked list of root of the tree, make left and right of root to point to itself. ….d) Concatenate leftList with the list of the single root node. ….e) Concatenate the list produced in the step above (d) with rightList. Note that the above code traverses the tree in Postorder fashion. We can traverse in an inorder fashion also. We can first concatenate left subtree and root, then recur for the right subtree and concatenate the result with left-root concatenation. How to Concatenate two circular DLLs? Get the last node of the left list. Retrieving the last node is an O(1) operation since the prev pointer of the head points to the last node of the list. Connect it with the first node of the right list Get the last node of the second list Connect it with the head of the list. Below are implementations of the above idea. ``` // C++ Program to convert a Binary Tree // to a Circular Doubly Linked List #include(iostream> using namespace std; ``` ``` // To represents a node of a Binary Tree struct Node { struct Node *left, *right; int data; }; ``` ``` // A function that appends rightList at the end // of leftList. Node *concatenate(Node *leftList, Node *rightList) { // If either of the list is empty // then return the other list if (leftList == NULL) return rightList; if (rightList == NULL) return leftList; ``` ``` // Store the last Node of left List Node *leftLast = leftList->left; ``` ``` // Store the last Node of right List Node *rightLast = rightList->left; ``` ``` // Connect the last node of Left List // with the first Node of the right List leftLast->right = rightList; rightList->left = leftLast; ``` ``` // Left of first node points to // the last node in the list leftList->left = rightLast; ``` ``` // Right of last node refers to the first // node of the List rightLast->right = leftList; ``` return leftList; } // Function converts a tree to a circular Linked List // and then returns the head of the Linked List Node *bTreeToCList(Node *root) { if (root == NULL) return NULL; ``` // Recursively convert left and right subtrees Node *left = bTreeToCList(root->left); Node *right = bTreeToCList(root->right); ``` ``` // Make a circular linked list of single node // (or root). To do so, make the right and // left pointers of this node point to itself root->left = root->right = root; ``` ``` // Step 1 (concatenate the left list with the list // with single node, i.e., current node) // Step 2 (concatenate the returned list with the // right List) return concatenate(concatenate(left, root), right); } ``` ``` // Display Circular Link List void displayCList(Node *head) { cout (( "Circular Linked List is :\n"; Node *itr = head; do { cout (( itr->data ((" "; itr = itr->right; } while (head!=itr); cout (( "\n"; } ``` ``` // Create a new Node and return its address Node *newNode(int data) { Node *temp = new Node(); temp->data = data; temp->left = temp->right = NULL; return temp; } ``` ``` // Driver Program to test above function int main() { Node *root = newNode(10); root->left = newNode(12); root->right = newNode(15); root->left->left = newNode(25); root->left->right = newNode(30); root->right->left = newNode(36); ``` Node *head = bTreeToCList(root); displayCList(head); return 0; } Output: Circular Linked List is : 25 12 30 10 36 15

Answer 4

Traverse the nextRight node before the left and right children (root, nextRight, left), then we can make sure that all nodes at level i have the nextRight set, before the level i+1 nodes. In this method, we make sure that all nodes at the 4’s level (level 2) have nextRight set, before we try to set the nextRight of 9. So when we set the nextRight of 9, we search for a nonleaf node on right side of node 4 (getNextRight() does this for us). 1 -------------- Level 0 / \ 2 3 -------------- Level 1 / \ / \ 4 5 6 7 -------------- Level 2 / \ / \ 8 9 10 11 -------------- Level 3 ``` class Solution { public: //Function to connect nodes at same level. void connect(Node *root) { //creating queue for level order traversal of tree. queue (Node*> q; q.push(root); ``` ``` //prev holds the value of previous node on the particular level. Node* prev=NULL; ``` ``` //end will hold value of last node of a level //and nextend will store the same for the next level. Node* end = root, *nextend; ``` ``` while(!q.empty()) { //storing the front element of queue in temp and popping it. Node* temp = q.front(); q.pop(); ``` ``` //storing all available nodes in queue and updating nextend. if(temp->left) { q.push(temp->left); nextend = temp->left; } if(temp->right) { q.push(temp->right); nextend = temp->right; } ``` ``` //setting nextRight of previous node of that level. if(prev) prev->nextRight = temp; ``` ``` //if we reach the end of a level, we set nextRight of the //current node and prev to NULL. if(temp == end) { temp->nextRight = NULL; prev = NULL; //we also set the value of end for next level. end = nextend; } //else we set prev to current node temp. else prev = temp; } } ``` };

Answer 5

Approach : Step 1: The simple method to solve this problem is we just creat first an array of Node having value at nodes from 0 to N-1 because we know from the question is that the indexes of parent array is represent values of Node and the value of parent array is represent the parent Node having this value of the Node having value equal to the index. step 2: Now we have an array of Nodes of tree. so we will traverse the parent array and will check if parent[i] = -1 then mark arr[i] as root of tree. if arr[parent[i]]->left or arr[parent[i]]->right is NULL then make arr[parent[i]]->left or arr[parent[i]]->right = arr[i] accordingly . step 3: Now return the root of tree. ``` class Solution{ public: //Function to construct binary tree from parent array. Node *createTree(int parent[], int N) { Node *arr[N]; Node *root; for(int i=0;i(N;i++) { arr[i] = new Node(i); } for(int i=0;i(N;i++) { if(parent[i]==-1) { root = arr[i]; } else { if(arr[parent[i]]->left==NULL) arr[parent[i]]->left = arr[i]; ``` ``` else if(arr[parent[i]]->right==NULL) arr[parent[i]]->right = arr[i]; } } return root; } }; ```

Answer 6

Method- (Check if Left and Right subtrees are Mirror) There are mainly two functions: 1. First function IsFoldable(root) which checks if tree can be folded or not. If tree is empty then return true Else check if left and right subtrees are structure wise mirrors of each other. Use utility function IsFoldableUtil(root->left,root->right) for this. 2. Second function IsFoldableUtil(n1, n2) which checks if two trees with roots n1 and n2 are mirror of each other. If both trees are empty then return true. If one of them is empty and other is not then return false. Return true if following conditions are met a) n1->left is mirror of n2->right b) n1->right is mirror of n2->left ``` //Function that checks if trees with roots n1 and n2 are mirror of each other. bool IsFoldableUtil(Node *n1, Node *n2) { //if both left and right subtrees are NULL then we return true. if (n1 == NULL && n2 == NULL) { return true; } ``` ``` //if one of the trees is NULL and other is not then we return false. if (n1 == NULL || n2 == NULL) { return false; } ``` ``` //else we check recursively if left and right subtrees are //mirrors of their counterparts. return IsFoldableUtil(n1->left,n2->right)&&IsFoldableUtil(n1->right,n2->left); } ``` ``` //Function to check whether a binary tree is foldable or not. bool IsFoldable(Node *root) { if (root == NULL) { return true; } return IsFoldableUtil(root->left, root->right); } ```

Answer 7

For each node there can be four ways that the max path goes through the node: 1. Node only 2. Max path through Left Child + Node 3. Max path through Right Child + Node 4. Max path through Left Child + Node + Max path through Right Child ``` The idea is to keep trace of four paths and pick up the max one in the end. An important thing to note is, root of every subtree needs to return maximum path sum such that at most one child of root is involved. This is needed for parent function call. class Solution { public: //Function to calculate maximum path sum. int findMaxUtil(Node *root, int &res) { //base case for recursion. if (root == NULL) return 0; ``` ``` //l and r store maximum path sum going recursively through left and //right subtrees of root(current node) respectively. int l = findMaxUtil(root->left, res); int r = findMaxUtil(root->right, res); ``` ``` //max path sum for parent call of root. This path must //include at-most one child of root. int max_single = max(max(l, r) + root->data, root->data); ``` ``` //max_top represents the sum when the node under consideration is the root //of the max sum path and no ancestors of root are there in max sum path. int max_top = max(max_single, l + r + root->data); ``` ``` //storing the maximum result. res = max(res, max_top); ``` return max_single; } ``` //Function to return maximum path sum from any node in a tree. int findMaxSum(Node *root) { int res = INT_MIN; findMaxUtil(root, res); ``` ``` //returning the result. return res; } }; ```

Answer 8

As we are given a binary tree, there is no relationship between node values so we need to traverse whole binary tree to get max difference and we can obtain the result in one traversal only by following below steps: If we are at leaf node then just return its value because it can’t be ancestor of any node. Then at each internal node we will try to get minimum value from left subtree and right subtree and calculate the difference between node value and this minimum value and according to that we will update the result. As we are calculating minimum value while returning in recurrence, we will check all optimal possibilities (checking node value with minimum subtree value only) of differences and hence calculate the result in one traversal only. ``` //Function to find the maximum difference. int maxDiffUtil(Node *t,int *res) { //returning Maximum int value if node is null. if (t == NULL) return INT_MAX; ``` ``` //if there are no child nodes then we just return data at current node. if (t->left == NULL && t->right == NULL) return t->data; ``` ``` //recursively calling for left and right subtrees and //choosing their minimum. int val = min(maxDiffUtil(t->left, res), maxDiffUtil(t->right, res)); ``` ``` //updating res if (node value - min value from subtrees) is bigger than res. *res = max(*res, t->data - val); ``` ``` //returning minimum value got so far. return min(val, t->data); } ``` ``` //Function to return the maximum difference between any node and its ancestor. int maxDiff(Node *root) { ```

Answer 9

Approach: There are mainly two functions: 1. First function countSubtreesWithSumX(root, count, x) which counts number of subtrees having sum equal to given sum. If root is null then return 0. Find the sum of left and right subtrees using the other function. If sum of left and right subtrees and data at current node is equal to given sum increment the counter. Return the count. 2. Second function countSubtreesWithSumXUtil(root, x) which find the sum of nodes in given subtree. If root is null then return 0. Find the sum of left and right subtrees recursively. If sum of left and right subtrees and data at current node is equal to given sum increment the counter. Return the sum. ``` //Function to find the sum of nodes in given subtree. int countSubtreesWithSumXUtil(Node* root, int& count, int x) { ``` if (!root) return 0; ``` //finding sum of nodes in the left and right subtrees recursively. int ls = countSubtreesWithSumXUtil(root->left, count, x); int rs = countSubtreesWithSumXUtil(root->right, count, x); int sum = ls + rs + root->data; ``` //if sum of ls, rs and current node data is equal to x, //we increment the counter. if (sum == x) count++; ``` //returning the sum. return sum; } ``` ``` //Function to count number of subtrees having sum equal to given sum. int countSubtreesWithSumX(Node* root, int x) { if (!root) return 0; int count = 0; ``` ``` //finding sum of nodes in the left subtrees. int ls = countSubtreesWithSumXUtil(root->left, count, x); ``` ``` //finding sum of nodes in the right subtrees. int rs = countSubtreesWithSumXUtil(root->right, count, x); ``` //if sum of ls,rs and current node data is equal to x, //we increment the counter. if ((ls + rs + root->data) == x) count++; ``` //returning the count. return count; } ```

Answer 10

Use DFS for serializing and deserializing. Make function call to child nodes once we are done with the parent node For serializing the tree into a list. If node is null, store -1 in list and return Store the data at current node in list. Call function recursively for left and right subtrees. Return the list. For deserializing the list into a tree. If there are no more elements in list, return null. Create new node for storing current element. Call function recursively for left and right subtrees. Return the tree. ``` class Solution { public: ``` ``` //Function to store the nodes of tree in the list. void serializeUtil(Node*root,vector(int>&a) { //base case if node is null. if (root == NULL) { a.push_back(-1); return; } //storing the data at node in list. a.push_back(root->data); ``` //calling function recursively for left and right subtrees. serializeUtil(root->left, a); serializeUtil(root->right, a); } ``` //Function to serialize a tree and return a list containing nodes of tree. vector(int> serialize(Node *root) { vector(int> serialized; serializeUtil(root,serialized); ``` ``` //returning the list. return serialized; } ``` ``` //Function to construct the tree. Node *kewl(vector(int> &a, int *index) { //base case if there are no more elements in list. if (*index == a.size() or a[*index] == -1) { *index += 1; return NULL; } ``` ``` //creating new node for storing current element. Node *root = new Node(a[*index]); *index += 1; ``` ``` //calling function recursively for left and right subtrees. root->left = kewl(a, index); root->right = kewl(a, index); return root; } ``` ``` //Function to deserialize a list and construct the tree. Node *deSerialize(vector(int> &a) { int index = 0; //returning the tree. return kewl(a, &index); } }; ```

Answer 11

``` void serAndPush(Node*root,vector(Node*>v,int k,set(Node*>&s){ if(root==NULL) return; v.push_back(root); serAndPush(root->left,v,k,s); serAndPush(root->right,v,k,s); if(root->left==NULL && root->right==NULL){ if(k>=v.size()) return; int t=0; for(int i=v.size()-1;i>=0;i--){ if(t==k){ s.insert(v[i]); return; } t++; } } } int printKDistantfromLeaf(Node* root, int k) { set(Node*>s; vector(Node*>v; serAndPush(root,v,k,s); return s.size(); } ```

Answer 12

This problem can be solved using two stacks. Assume the two stacks are current: currentlevel and nextlevel. We would also need a variable to keep track of the current level order (whether it is left to right or right to left). We pop from the currentlevel stack and print the nodes value. Whenever the current level order is from left to right, push the nodes left child, then its right child to the stack nextlevel. Since a stack is a LIFO(Last-In-First-out) structure, next time when nodes are popped off nextlevel, it will be in the reverse order. On the other hand, when the current level order is from right to left, we would push the nodes right child first, then its left child. Finally, do-not forget to swap those two stacks at the end of each level (i.e., when current level is empty) ``` class Solution{ public: //Function to store the zig zag order traversal of tree in a list. vector (int> zigZagTraversal(Node* root) { vector (int> res; ``` ``` //if root is null, we return the list. if (!root)return res; ``` ``` //declaring two stacks to store the current and new level. stack(struct Node*> currentlevel; stack(struct Node*> nextlevel; ``` ``` //pushing the root in currentlevel stack. currentlevel.push(root); bool lefttoright = true; ``` ``` while (!currentlevel.empty()) { //storing the top element of currentlevel stack in temp and popping it. Node* temp = currentlevel.top(); currentlevel.pop(); ``` //if temp is not null, we store the data at temp in list. if (temp) { res.push_back (temp->data); ``` //if lefttoright is true then it stores nodes from left to right //else from right to left in nextlevel stack. if (lefttoright) { if (temp->left) nextlevel.push(temp->left); if (temp->right) nextlevel.push(temp->right); } else { if (temp->right) nextlevel.push(temp->right); if (temp->left) nextlevel.push(temp->left); } } ``` ``` //if currentlevel stack is empty lefttoright is flipped to change //the order of storing the nodes and both stacks are swapped. if (currentlevel.empty()) { lefttoright = !lefttoright; swap(currentlevel, nextlevel); } } //returning the list. return res; } }; ```

Answer 13

Return a pair for each node in the binary tree such that the first of the pair indicates maximum sum when the data of a node is included and the second indicates maximum sum when the data of a particular node is not included. ``` class Solution{ public: //Function which returns a pair such that first of the pair indicates maximum //sum when data of a node is included and the second when it is not included. pair(int, int> maxSumHelper(Node *root) { //if root is null, we return two zeroes in pair. if (root==NULL) { pair(int, int> sum(0, 0); return sum; } ``` ``` //calling function recursively for left and right subtrees. pair(int, int> sum1 = maxSumHelper(root->left); pair(int, int> sum2 = maxSumHelper(root->right); pair(int, int> sum; ``` ``` //current node is included (Left and right children are not included). sum.first = sum1.second + sum2.second + root->data; ``` ``` //current node is excluded (Either left or right child is included). sum.second = max(sum1.first, sum1.second) + max(sum2.first, sum2.second); ``` return sum; } ``` //Function to return the maximum sum of non-adjacent nodes. int getMaxSum(Node *root) { pair(int, int> res = maxSumHelper(root); //returning the maximum between the elements in pair(res). return max(res.first, res.second); } }; ```