Populating next right pointer
TC: O(N), where N is no. of nodes in the tree
import java.util.*; public class Solution { public static void connectNodes(BinaryTreeNode<Integer> root) { // Write your code here. // we will use level order traversal for this Queue<BinaryTreeNode<Integer>> q = new LinkedList<>(); if(root==null) return; q.add(root); while(!q.isEmpty()){ int size = q.size(); BinaryTreeNode<Integer> prev = null; for(int i = 0;i<size;i++){ BinaryTreeNode<Integer> node = q.remove(); node.next= prev; prev = node; if(node.right!=null) q.add(node.right); if(node.left!=null)q.add(node.left); } } } } Convert Sorted Array to binary search tree
Given an integer array nums where the elements are sorted in ascending order, convert it to a height-balanced binary search tree.
TC: o(logn) as we are dividing the array into two equals halves which makes it same as binary search algorithm
/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode() {} * TreeNode(int val) { this.val = val; } * TreeNode(int val, TreeNode left, TreeNode right) { * this.val = val; * this.left = left; * this.right = right; * } * } */ class Solution { public TreeNode sortedArrayToBST(int[] nums) { return createBST(0,nums.length-1,nums); } public TreeNode createBST(int start, int end,int nums[]){ if(start > end) return null; int mid = start + (end-start)/2; TreeNode node = new TreeNode(nums[mid]); node.left = createBST(start,mid-1,nums); node.right = createBST(mid+1,end,nums); return node; } } Construct preorder traversal from binary search tree
TC: O(nlogn) + O(n), where nlogn for sorting the array,
/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode() {} * TreeNode(int val) { this.val = val; } * TreeNode(int val, TreeNode left, TreeNode right) { * this.val = val; * this.left = left; * this.right = right; * } * } */ class Solution { public TreeNode bstFromPreorder(int[] preorder) { int index =0; int sortedArray[] = new int[preorder.length]; Queue<Integer> q = new LinkedList<>(); for(int i =0;i< sortedArray.length;i++){ sortedArray[i] = preorder[i]; q.add(preorder[i]); } Arrays.sort(sortedArray); return createBst(0,sortedArray.length-1,q,sortedArray); } public TreeNode createBst(int start, int end, Queue<Integer> q,int[] sortedArray){ if(start > end) return null; int rootVal = q.remove(); TreeNode node = new TreeNode(rootVal); int mid = binarySearch(start,end,rootVal,sortedArray); node.left = createBst(start,mid-1,q,sortedArray); node.right = createBst(mid+1,end,q,sortedArray); return node; } public int binarySearch(int start, int end,int target, int[] arr){ if(start > end) return -1; int mid = start + (end-start)/2; if(arr[mid] == target) return mid; if(arr[mid] > target){ return binarySearch(start,mid-1, target, arr); } return binarySearch(mid+1, end, target,arr); } Optimized solution :
TC: O(3N) which is O(n)
//for more idea see this https://www.youtube.com/watch?v=UmJT3j26t1I class Solution { public TreeNode bstFromPreorder(int preorder[]){ return generateBST(preorder, new int[]{0},Integer.MAX_VALUE); //0 indicates the current pointer of the element that needs to be inserted //Integer.MAX_VALUE is max bound } public TreeNode generateBST(int[] pre,int pointer[], int bound){ if(pointer[0] > pre.length-1 || pre[pointer[0]] > bound) return null; TreeNode node = new TreeNode(pre[pointer[0]++]);// value at pointer has been added to the tree, now move to next value int the array node.left = generateBST(pre,pointer,node.val); // now node.val will become bound for all the // elements to the left of node, as they can't be equal to or greater than node.val node.right = generateBST(pre,pointer,bound);//for the right subtree bound will remain same return node; } 
Top comments (0)