Category: java

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 ,…

Valid Binary Search Tree (BST) or not?
You are given a binary search tree. You need to find out if it is valid or not. A BST is valid if all the elements in the left tree are less than the current node And all the elements in the right tree are greater than the current node. This has to apply for…

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:…

Level Order Traversal of a Binary Tree
Given the root of a binary tree , return the level order traversal of the binary tree . Level order traversal means picking nodes from left to right level by level. For example, For the below tree: Level order traversal is [[3],[9,20],[15,7]] It is a list of lists. Each list represent the nodes at that…

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.…

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…

Data Structures & Algorithms in Java – Graphs – Alien Dictionary.
Problem: You are given a list of English words arranged lexically (as in a dictionary). But not in the order of English alphabets but in the order of an alien language which uses English script. With the given words you need to arrange the letters in the right order of the alien dictionary. For example,…

Data Structures & Algorithms in Java – Graphs – Valid Tree
Problem: Given the number of nodes in a graph and the list of edges in the graph , find if it is a valid tree. For example, Given n = 5 and the edges [[0,1] ,[0,2],[0,3],[3,4] It is a valid tree because there are no cycles in it and every node is connected with an…