CSE Company Interview Questions

PROBLEM : Implement an iterator over a binary search tree (BST). Your iterator will be initialized with the root node of a BST. Calling next() will return the next smallest number in the BST. Note: next() and hasNext() should run in average O(1) time and uses O(h) memory, where h is the height of the tree. -------------------------------------------------------------------------------- SIMPLE c++ IMPLEMENTATION : -------------------------------------------------------------------------------- /**  * Definition for binary tree  * struct TreeNode {  *     int val;  *     TreeNode *left;  *     TreeNode *right;  *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}  * };  */ class BSTIterator {     stack<TreeNode *> sta ; public:     BSTIterator(TreeNode *root) {         pushLeft(root) ;     }     /** @return wh...

PROBLEM : Given two Binary Search Trees, task is to complete the function printCommon, which print's the common nodes in them. In other words, find intersection of two BSTs. Example root1                  5               /    \             1       10           /   \    /          0     4   7                     \                      9 root2:                10              /    \             7     20           /   \          4     9 Output: 4 7 9 10 Input: Th...

PROBLEM : Given the root of a binary tree, then value v and depth d, you need to add a row of nodes with value v at the given depth d. The root node is at depth 1. The adding rule is: given a positive integer depth d, for each NOT null tree nodes N in depth d-1, create two tree nodes with value v as N's left subtree root and right subtree root. And N's original left subtree should be the left subtree of the new left subtree root, its original right subtree should be the right subtree of the new right subtree root. If depth d is 1 that means there is no depth d-1 at all, then create a tree node with value v as the new root of the whole original tree, and the original tree is the new root's left subtree. Example 1: Input: A binary tree as following:        4      /   \     2     6    / \   /   3   1 5   v = 1 d = 2 Output:        4       / \ ...

PROBLEM : You need to construct a string consists of parenthesis and integers from a binary tree with the preorder traversing way. The null node needs to be represented by empty parenthesis pair "()". And you need to omit all the empty parenthesis pairs that don't affect the one-to-one mapping relationship between the string and the original binary tree. Example 1: Input: Binary tree: [1,2,3,4]        1      /   \     2     3    /     4     Output: "1(2(4))(3)" Explanation: Originallay it needs to be "1(2(4)())(3()())", but you need to omit all the unnecessary empty parenthesis pairs. And it will be "1(2(4))(3)". Example 2: Input: Binary tree: [1,2,3,null,4]        1      /   \     2     3      \       4 Output: "1(2()(4))(3)" Explanation: Almost the same as the first example, ...

PROBLEM : Given two non-empty binary trees s and t, check whether tree t has exactly the same structure and node values with a subtree of s. A subtree of s is a tree consists of a node in s and all of this node's descendants. The tree s could also be considered as a subtree of itself. Example 1: Given tree s:      3     / \    4   5   / \  1   2 Given tree t:    4   / \  1   2 Return true, because t has the same structure and node values with a subtree of s. Example 2: Given tree s:      3     / \    4   5   / \  1   2     /    0 Given tree t:    4   / \  1   2 Return false. -------------------------------------------------------------------------------- SIMPLE c++ IMPLEMENTATION : -------------------------------------------------------------------------------- /** ...

PROBLEM : Given a binary tree, return the tilt of the whole tree. The tilt of a tree node is defined as the absolute difference between the sum of all left subtree node values and the sum of all right subtree node values. Null node has tilt 0. The tilt of the whole tree is defined as the sum of all nodes' tilt. Example: Input:          1        /   \       2     3       Output: 1 Explanation: Tilt of node 2 : 0 Tilt of node 3 : 0 Tilt of node 1 : |2-3| = 1 Tilt of binary tree : 0 + 0 + 1 = 1 Note: The sum of node values in any subtree won't exceed the range of 32-bit integer. All the tilt values won't exceed the range of 32-bit integer. -------------------------------------------------------------------------------- SIMPLE c++ IMPLEMENTATION : -------------------------------------------------------------------------------- /**  * Definition for a binary tree no...

PROBLEM : A binary tree and a number k are given. Print the count of every path in the tree with sum of the nodes in the path as k. Input: First line consists of T test cases. First line of every test case consists of N, denoting the number of Node is Binary tree. Second line consists of N spaced 3 elements denoting the Parent node, Child Node and a character denoting left or right child. Third line of every test case consists of a integer K. Output: Return the Count of number of paths in tree. Constraints: 1<=T<=20 1<=N<=100 Example: Input: 1 4 1 3 L 3 2 L 3 -1 R -1 1 R 4 Output: 2 -------------------------------------------------------------------------------- SIMPLE c++ IMPLEMENTATION : -------------------------------------------------------------------------------- /*Complete the function below Node is as follows: struct Node{ int data; Node *left,*right; Node(int d){ data=d; left=right=NULL; } };*/ int CountKSum(Node *,i...

PROBLEM : Given a root of the tree you need to perform AVL tree deletion operations on it. You need to complete the method delelteNode which takes 2 arguments the first is the root of the tree and the second is the value of the node to be deleted.The function should return the root of the modified tree. Note: Your code will be checked for each insertion and will produce an output 1 if all the nodes for a particular test case were correctly inserted else 0. Input: The first line of input contains an integer T denoting the no of test cases. Then T test cases follow. Each test case contains 2 lines . The first line of each test case contains an integer N denoting the no of nodes to be inserted in the AVL tree and in the next line are N space separated values denoting the values of the nodes to be inserted to the tree. And last line denotes the element to be deleted. Output: For each test case output will be 1 if the node was correctly deleted else 0. Constraints: 1<=T...

PROBLEM : Given two binary trees and imagine that when you put one of them to cover the other, some nodes of the two trees are overlapped while the others are not. You need to merge them into a new binary tree. The merge rule is that if two nodes overlap, then sum node values up as the new value of the merged node. Otherwise, the NOT null node will be used as the node of new tree. Example 1: Input: Tree 1                     Tree 2                           1                         2                                      / \                       / \                               ...

PROBLEM : You need to find the largest value in each row of a binary tree. Example: Input:           1          / \         3   2        / \   \       5   3   9 Output: [1, 3, 9] -------------------------------------------------------------------------------- SIMPLE c++ IMPLEMENTATION : -------------------------------------------------------------------------------- /**  * Definition for a binary tree node.  * struct TreeNode {  *     int val;  *     TreeNode *left;  *     TreeNode *right;  *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}  * };  */ class Solution { public:     vector<int> largestValues(TreeNode* root) {                 vector<int> vec ;        ...

PROBLEM : You are given a binary tree in which each node contains an integer value. Find the number of paths that sum to a given value. The path does not need to start or end at the root or a leaf, but it must go downwards (traveling only from parent nodes to child nodes). The tree has no more than 1,000 nodes and the values are in the range -1,000,000 to 1,000,000. Example: root = [10,5,-3,3,2,null,11,3,-2,null,1], sum = 8       10      /  \     5   -3    / \    \   3   2   11  / \   \ 3  -2   1 Return 3. The paths that sum to 8 are: 1.  5 -> 3 2.  5 -> 2 -> 1 3. -3 -> 11 -------------------------------------------------------------------------------- SIMPLE c++ IMPLEMENTATION : -------------------------------------------------------------------------------- /**  * Definition for a binary tree node.  * struct TreeNod...

PROBLEM : Given root of binary search tree and K as input, find K-th smallest element in BST. Your task is to return the K-th smallest element in BST from the function k_smallest_element(). Note: The Time Complexity will be O(h) where h is the height of the Tree. Input: The first line of input will contain the number of test cases T. Then T test cases follow. First line of every test case will be n, denoting the number of nodes in the BST. Second line of every test case will be n spaced integers denoting the Integer value of Nodes in BST. Third line of every test case will be k, denoting kth the smallest number. Output: For each test case, output will be the kth smallest element of BST. Constraints: 1<=T<=100 1<=N<=100 1<=K<=N Example(To be used only for expected output): Input: 1 5 20 8 4 22 12 3 Output: 12 -------------------------------------------------------------------------------- SIMPLE c++ IMPLEMENTATION : -----------------------...

PROBLEM : Given a Binary Search Tree and a target sum, write a function that returns true if there is a pair with sum equals to target sum, otherwise return false. Input: First line consists of T test cases. First line of every test case consists of N and target, denoting the number of elements in bst and target sum. Second line consists of elements of BST. Output: Return True if target sum pair is found else False. Constraints: 1<=T<=100 1<=N<=100 Example: Input: 2 7 10 1 2 3 4 5 6 7 7 33 15 10 20 8 12 16 25 Output: 1 1 -------------------------------------------------------------------------------- SIMPLE c++ IMPLEMENTATION : -------------------------------------------------------------------------------- /*Complete the function below Node is as follows struct node {     int val;     struct node *left, *right; }; */ bool isPairPresent(struct node *root, int target) {     if(!root)      ...

PROBLEM : Given a BST,  and a reference to a Node x the task is to find the Inorder Successor of the node . Input: The first line of input contains an integer T denoting the no of test cases. Then T test cases follow.  The second line consist of an integer N. Then in the next line are N space separated values of the BST nodes. In the next line is an integer x representing the value of the node in the BST. Output: For each test case output will be the Inorder successor of the given node. If no such successor is present output will be -1. Constraints: 1<=T<=100 1<=N<1100 1<=A[]<=1000 Example: Input: 2 7 20 8 22 4 12 10 14 8 7 20 8 22 4 12 10 14 10 Output: 10 12 -------------------------------------------------------------------------------- SIMPLE c++ IMPLEMENTATION : -------------------------------------------------------------------------------- /*The structure of Node struct Node { int data; Node * right, * left; };*/ ...

PROBLEM : Given an array that represents a Tree in such a way that array indexes are values in tree nodes and array values give the parent node of that particular index (or node). The value of the root node index would always be -1 as there is no parent for root. Construct the standard linked representation of given Binary Tree from this given representation. The Binary tree  node structure has 3 fields, a data part which stores the data, a left pointer which points to the left element of the tree and a right pointer which points to the right node of the  tree. There are multiple test cases. For each test case, this function will be called individually. Input: The first line of the input contains an integer 'T' denoting the number of test cases. Then 'T' test cases follow. Each test case consists of two lines. First line of each test case contains an integer N denoting the size of the tree array . Second line of each test case consists of 'N' space sep...

PROBLEM : Given a binary tree, return all root-to-leaf paths. For example, given the following binary tree:    1  /   \ 2     3  \   5   All root-to-leaf paths are: ["1->2->5", "1->3"] -------------------------------------------------------------------------------- SIMPLE c++ IMPLEMENTATION : -------------------------------------------------------------------------------- /**  * Definition for a binary tree node.  * struct TreeNode {  *     int val;  *     TreeNode *left;  *     TreeNode *right;  *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}  * };  */ class Solution { public:     vector<string> binaryTreePaths(TreeNode* root) {         vector<string> vec ;         if(root==NULL)             return vec ;   ...

PROBLEM : Given a binary search tree, write a function kthSmallest to find the kth smallest element in it. Note: You may assume k is always valid, 1 ? k ? BST's total elements. -------------------------------------------------------------------------------- SIMPLE c++ IMPLEMENTATION : -------------------------------------------------------------------------------- /**  * Definition for a binary tree node.  * struct TreeNode {  *     int val;  *     TreeNode *left;  *     TreeNode *right;  *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}  * };  */ class Solution { public:     int kthSmallest(TreeNode* root, int k) {         int min ;         KthSallestEle(root,&k,&min) ;         return min ;     }         void KthSallestEle(TreeNode *root,int *k,int *min){  ...

PROBLEM : Given a binary tree, imagine yourself standing on the right side of it, return the values of the nodes you can see ordered from top to bottom. For example: Given the following binary tree,    1            <---  /   \ 2     3         <---  \     \   5     4       <--- You should return [1, 3, 4].     -------------------------------------------------------------------------------- SIMPLE c++ IMPLEMENTATION : -------------------------------------------------------------------------------- /**  * Definition for a binary tree node.  * struct TreeNode {  *     int val;  *     TreeNode *left;  *     TreeNode *right;  *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}  * };  */ class Solution { public:     vector...

PROBLEM : Given a binary tree containing digits from 0-9 only, each root-to-leaf path could represent a number. An example is the root-to-leaf path 1->2->3 which represents the number 123. Find the total sum of all root-to-leaf numbers. For example,     1    / \   2   3 The root-to-leaf path 1->2 represents the number 12. The root-to-leaf path 1->3 represents the number 13. Return the sum = 12 + 13 = 25.     -------------------------------------------------------------------------------- SIMPLE c++ IMPLEMENTATION : -------------------------------------------------------------------------------- /**  * Definition for a binary tree node.  * struct TreeNode {  *     int val;  *     TreeNode *left;  *     TreeNode *right;  *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}  * };  */ class Solution { public:   ...

PROBLEM : Given a binary tree, flatten it to a linked list in-place. For example, Given          1         / \        2   5       / \   \      3   4   6     The flattened tree should look like:    1     \      2       \        3         \          4           \            5             \              6     -------------------------------------------------------------------------------- SIMPLE c++ IMPLEMENTATION : -------------------------------------------------------------------------------- /**  * Definition for a binary tree node.  * struct TreeNode {  *     ...