Vertical Order Traversal of a Binary Tree - Google Interview Question

Рет қаралды 7,789

6 ай бұрын

Learn how to solve the Vertical Order Traversal LeetCode problem frequently asked in Google interviews with this easy-to-understand, step-by-step tutorial.
Take part in the learning in public initiative! Share your learnings on LinkedIn and Twitter with #DSAwithKunal & don't forget to tag us!
👉 Resources
- Join Replit: join.replit.com/kunal-kushwaha
- Lecture code: replit.com/@KunalsReplit/Adva...
- Complete Java DSA playlist: • Java + DSA + Interview...
- Code, Assignments, & Notes: github.com/kunal-kushwaha/DSA...
➡️ Connect with me: kunalkushwaha.com
👨‍💻 Join WeMakeDevs: wemakedevs.org
#dsa #placement #leetcode

Пікірлер: 24

@KunalKushwaha 6 ай бұрын

👉 Resources - Join Replit: join.replit.com/kunal-kushwaha - Lecture code: replit.com/@KunalsReplit/AdvanceTreeQuestions

@varunsalian3909 5 ай бұрын

Hi thanks for your efforts, have learnt a lot from your playlist, in this particular question you seem to have missed a use case, quoting from leetcode "There may be multiple nodes in the same row and same column. In such a case, sort these nodes by their values." Your code fails in leetcode for this particular use case.

@Sranju23 4 ай бұрын

yeah looks like solution is for the LC # 314 instead

@sohansingh2022 6 ай бұрын

Thanks. Hope you are well😊

@supunherath4808 6 ай бұрын

thanks a lot for doing this ❤

@NareshNaresh-cl8rn Ай бұрын

Sir i am thankful for dsa playlist please complete the course sir

@vakeelsaab5323 6 ай бұрын

Thanks Kunal

@erenyeager3659 6 ай бұрын

hey @kunalKushwaha does learning spring help in my career is there any future for java devoloper

@DurgeshChauhan-lq8wq 6 ай бұрын

Bhaiya dec end TK course complete ho jayega na please reply

@SiliO_ 6 ай бұрын

bro please suggest me graphs and dp best resource

@karthik_macharla 27 күн бұрын

Hi Kunal, we're waiting for DP and Graphs playlist

@preetichib2254 5 ай бұрын

great explaination

@veerendrasaikumar1008 4 ай бұрын

Thanks for the great explanation, as per leet code description, Kunal, you missed to sort the elements with the same row and same column while adding it into the ans arraylist

@SarcasticAI-wh3mf 2 ай бұрын

below code works class Solution { class Tuple{ TreeNode node; Integer col; Integer row; Tuple(TreeNode n,Integer c,Integer r){ node = n; col = c; row = r; } } public List verticalTraversal(TreeNode node) { List ans = new ArrayList(); if (node == null) { return ans; } int col = 0; int row = 0; Queue queue = new ArrayDeque(); TreeMap map = new TreeMap(); queue.offer(new Tuple(node, col,row)); int min = 0; int max = 0; while(!queue.isEmpty()) { Tuple removed = queue.poll(); node = removed.node; col = removed.col; row = removed.row; if(node != null) { map.putIfAbsent(col, new TreeMap()); map.get(col).putIfAbsent(row, new PriorityQueue()); map.get(col).get(row).add(node.val); min = Math.min(min, col); max = Math.max(max, col); queue.offer(new Tuple(node.left, col-1,row+1)); queue.offer(new Tuple(node.right, col+1,row+1)); } } // Loop through the map and add the values. // x -> key, (y, nodes) -> values. for (TreeMap yn : map.values()) { // Create a sublist to store node values in each vertical. List sublist = new ArrayList(); // Iterate over the PriorityQueue and add nodes to the sublist. for (PriorityQueue nodes : yn.values()) { while (!nodes.isEmpty()) { sublist.add(nodes.poll()); } } // Add the sublist to the ans list. ans.add(sublist); } return ans; } }