Tag: tree

Is a Tree Symmetric?
Given a binary tree find out if it is symmetric or not. A tree is symmetric if it is left sub tree is a reflection of its right sub tree. Note that symmetry doesn’t mean left sub tree is equal to right sub tree. The following tree is a symmetric tree: As you see the…

Serialize and Deserialize a Tree
Given the root node of a tree , serialize it into a string. Given a serialized string , construct a tree and return the true node. Try out the solution here: https://leetcode.com/problems/serializeanddeserializebinarytree/ Solution: Serialization: First do a preorder traversal of the tree and store the node values in a string. If node is null store…

Find the Lowest Common Ancestor of two given nodes of a Binary Search Tree
Given two nodes and the root node of a binary search tree, Find the lowest common ancestor of those two nodes. A common ancestor node is a node who is the parent of both the given nodes. Lowest common ancestor means there is no other common ancestor node which is lower than this node in…

Kth Smallest Element in a Binary Search Tree
Given a binary search tree, find the kth smallest element in it. For example, For the below tree: If k = 3, Then the kth (3rd) smallest element is 3. If k = 2, Then the output is 2. Try out the solution here: https://leetcode.com/problems/kthsmallestelementinabst/ Solution: Hint : Use inorder traversal. Explanation: Approach 1 –…

Construct Binary Tree From Preorder and Inorder Traversals
Given the preorder and inorder traversal arrays of a tree, construct it. For example, Given preorder = [3,9,20,15,7], inorder = [9,3,15,20,7] You need to construct the below tree: you need to return the root node of the above tree in your code. Try it here: https://leetcode.com/problems/constructbinarytreefrompreorderandinordertraversal/ Solution: Hint: Using root node from preorder traversal ,…

Subtree of Another Tree
Given two trees, check if the second tree is a subtree of the first tree For example, Consider the below trees : As evident from the diagram , the subRoot tree is a subtree of root. The input is : root = [3,4,5,1,2], subRoot = [4,1,2] The output is true Try out the solution here:…

Maximum Path Sum in a Binary Tree
Given a binary tree, find the maximum path sum . A path is a sequence of nodes connected by edges. You can start from any node and go to any node in the tree as long as they are connected by edges. Also the same node cannot be present more than one in the sequence.…

Invert Binary Tree
Given a tree , invert it. That is its left node becomes its right node and this follows for every node in each level of the tree. Similarly for the right node. For example: Given the tree: [4,2,7,1,3,6,9] The output is : [4,7,2,9,6,3,1] Try out the solution here: https://leetcode.com/problems/invertbinarytree/ Solution: Use DFS or BFS Approach…

Same Tree or Not?
Given the root node of two trees, find if they are the same . For example: The below trees: [1,2,3] and [1,2,3] are the same [1,2] and [1,2,3] are not same. Note that though the given input is two arrays above, you can’t just compare each value of one array with the other array. The…

Maximum Depth of a Binary Tree
Given a tree data structure , write an algorithm to find the maximum depth of the tree. Maximum depth is the length of the path from root node to the most distant leaf of the tree. For example: Given a tree represented by the array: [3,9,20,null,null,15,7] where each three elements in the array represents the…