InterviewReady

  Given two integer arrays   preorder   and   inorder   where   preorder   is the preorder traversal of a binary tree and   inorder   is the inorder traversal of the same tree, construct and return   the binary tree .   Example 1: Input: preorder = [3,9,20,15,7], inorder = [9,3,15,20,7] Output: [3,9,20,null,null,15,7] Example 2: Input: preorder = [-1], inorder = [-1] Output: [-1]

Given the   root   of a Binary Search Tree (BST), convert it to a Greater Tree such that every key of the original BST is changed to the original key plus the sum of all keys greater than the original key in BST. As a reminder, a  binary search tree  is a tree that satisfies these constraints: The left subtree of a node contains only nodes with keys  less than  the node's key. The right subtree of a node contains only nodes with keys  greater than  the node's key. Both the left and right subtrees must also be binary search trees. Example 1: Input: root = [4,1,6,0,2,5,7,null,null,null,3,null,null,null,8] Output: [30,36,21,36,35,26,15,null,null,null,33,null,null,null,8] Example 2: Input: root = [0,null,1] Output: [1,null,1] Solution class Solution { int pre = 0; public TreeNode bstToGst(TreeNode root) { if (root.right != null) bstToGst(root.right); pre = root.val = pre + root.val; if (root.left != null) bs...

  class Solution {     public int minDepth (TreeNode root) {                 if (root == null) return 0; if (root.left == null) return minDepth(root.right) + 1; if (root.right == null) return minDepth(root.left) + 1; return Math.min(minDepth(root.left),minDepth(root.right)) + 1;             } }

  Given the   root   of a binary tree,   check whether it is a mirror of itself   (i.e., symmetric around its center).   Example 1: Input: root = [1,2,2,3,4,4,3] Output: true Example 2: Input: root = [1,2,2,null,3,null,3] Output: false class Solution { public boolean isSymmetric(TreeNode root) { return isMirror(root.left, root.right); } public boolean isMirror(TreeNode t1, TreeNode t2) { if(t1==null && t2==null) return true; if(t1==null || t2==null) return false; return t1.val==t2.val && isMirror(t1.left, t2.right) &&                                     isMirror(t1.right, t2.left); } }

  Given the   root   of a binary tree,   determine if it is a valid binary search tree (BST) . A  valid BST  is defined as follows: The left subtree of a node contains only nodes with keys  less than  the node's key. The right subtree of a node contains only nodes with keys  greater than  the node's key. Both the left and right subtrees must also be binary search trees. Not a valid Binary tree as 4 is less than 5. Largest element in left subtree < root.val < Smallest element in left sub tree Binary Tree Inorder traversal gives sorted elements. Example 1: Input: root = [2,1,3] Output: true Example 2: Input: root = [5,1,4,null,null,3,6] Output: false Explanation: The root node's value is 5 but its right child's value is 4. To solve this we will apply Depth First Search. Code class Solution {     public TreeNode prev = null;     public boolean isValidBST(TreeNode root) {          ...

  Given the   root   of a binary tree, return   the inorder traversal of its nodes' values .   Example 1: Input: root = [1,null,2,3] Output: [1,3,2] Example 2: Input: root = [] Output: [] Example 3: Input: root = [1] Output: [1] class Solution { List<Integer> list = new ArrayList<Integer>(); public List<Integer> inorderTraversal(TreeNode root) { if(root==null) return new ArrayList<Integer>(); inorderTraversal(root.left); list.add(root.val); inorderTraversal(root.right); return list; } }

Given the  root  of a binary tree, return  its maximum depth . A binary tree's  maximum depth  is the number of nodes along the longest path from the root node down to the farthest leaf node.  Example 1: Input: root = [3,9,20,null,null,15,7] Output: 3 Example 2: Input: root = [1,null,2] Output: 2 class Solution { public int maxDepth(TreeNode root) { if(root==null) return 0; int d1 = maxDepth(root.left); int d2 = maxDepth(root.right); return Math.max(d1,d2)+1; } } Explanation 1. Calculate the depth of the left subtree and right tree. 2. Get max of left and right sub tree. 3. Depth of tree is max + 1 as include root node also. 4. Base condition is root is null then return 0.

We have all watched trees from our childhood. It has roots, stems, branches and leaves. It was observed long back that each leaf of a tree can be traced to root via a unique path. Hence tree structure was used to explain hierarchical relationships, e.g. family tree, animal kingdom classification, etc. This hierarchical structure of trees is used in Computer science as an abstract data type for various applications like data storage, search and sort algorithms. A tree is a hierarchical data structure defined as a collection of nodes. Nodes represent value and nodes are connected by edges. A tree has the following properties: The tree has one node called root. The tree originates from this, and hence it does not have any parent. Each node has one parent only but can have multiple children. Each node is connected to its children via edge. Terminology 1. Root is a special node in a tree. The entire tree originates from it. It does not have a parent. 2. Parent node is an immediate predecess...

  public class TreeNode { Integer value ; TreeNode left ; TreeNode right ; public TreeNode(Integer value) { this . value = value; } public Integer getValue() { return value ; } public void setValue(Integer value) { this . value = value; } public TreeNode getLeft() { return left ; } public void setLeft(TreeNode left) { this . left = left; } public TreeNode getRight() { return right ; } public void setRight(TreeNode right) { this . right = right; } } public class TreeTraversal { public static TreeNode createTree() { TreeNode rootNode = new TreeNode( 9 ); TreeNode node1 = new TreeNode( 7 ); TreeNode node2 = new TreeNode( 10 ); TreeNode node3 = new TreeNode( 3 ); TreeNode node4 = new TreeNode( 8 ); rootNode.setLeft(node1); rootNode.setRight(node2); node1.setLeft(node3); node1.setRight(...