Kodr

Kodr

  • Content
  • Blog
  • About
  • Languages iconEnglish
    • Español

›Problems: Binary Search Trees & Graphs

Technical Interviews

  • What are technical interviews based on?
  • Essential content & how to solve algorithms

Big-O Notation

  • Big-O Notation
  • Big-O Examples
  • Big-O Exercises

Optimisation Techniques

  • BUD optimisation
  • DIY Optimisation

Key Concepts

  • Linked Lists
  • Stack & Queues
  • Trees
  • Graphs
  • Tries
  • Sorting
  • Searching
  • Recursion
  • Dynamic Programming

Problems: Arrays & Strings

  • Is Unique
  • String Rotation
  • Check Permutation
  • URLify
  • One Edit Away
  • String Compression
  • Rotate Matrix
  • Zero Matrix
  • Valid Parenthesis

Problems: Linked Lists

  • Remove duplicates
  • Kth to last node
  • Delete Middle Node
  • Partition
  • Sum List
  • Palindrome
  • Intersection
  • Loop Detection

Problems: Stacks & Queues

  • Stack Min
  • Stack Of Plates
  • Queue via Stacks
  • Sort Stack
  • Animal Shelter

Problems: Trees

  • Path Sum
  • Construct Binary Tree from Inorder and Postorder Traversal

Problems: Binary Search Trees & Graphs

  • Route Between Two Nodes
  • Minimal Tree
  • List of Depths
  • Check Balanced
  • Validate BST
  • Successor
  • Build Order
  • First Common Ancestor
  • Check Sub-Tree
  • (Harder) Random Node

Problems: Sorting & Searching

  • Merge Sorted Array
  • First Bad Version

Problems: Dynamic Programming

  • Triple Step
  • Magic Index
  • (Hard) Towers Of Hanoi

List of Depths

Given a binary tree, design an algorithm which creates a linked list of all the nodes at each depth (e.g., if you have a tree with depth D, you'll have D linked lists).

👉 Link here to the repo to solve the problem

imagen

👌 Tips

Try modifying a graph search algorithm to track the depth from the root.

A hash table or array that maps from level number to nodes at that level might also be useful.

You should be able to come up with an algorithm involving both depth-first search and breadth-first search.

👊 Solution 1

This solution uses a recursive approach where I create a list of list to keep track of each level, list.get(0) will be the top layer, list.get(1) will be the second layer from the top, etc.

I do it in a very similar approach as preOrderTraversal (reference in the tree section). Where I visit a node, add that value to the list of lists and move onto the children whilst increasing the counter by one.

imagen

public class ListOfDepths {
     List<List<Integer>> solution(BinaryTreeNode head) {
         int counter = 0;
         List<List<Integer>> listOfLists = new ArrayList<>();
         traverseAndAppend(listOfLists, head, counter);
         return listOfLists;
     }

     private void traverseAndAppend(List<List<Integer>> list, BinaryTreeNode node, int counter) {
         if (node != null) {
             addToList(list, counter, node.data);
             traverseAndAppend(list, node.left, counter + 1);
             traverseAndAppend(list, node.right, counter + 1);
         }
     }

     private void addToList(List<List<Integer>> list, int counter, int value) {
         try {
             list.get(counter).add(value);
         } catch (IndexOutOfBoundsException error) {
             list.add(counter, new ArrayList<>());
             list.get(counter).add(value);
         }
     }
}

Question borrowed from “Cracking the coding interview”

Last updated on 3/19/2020
← Minimal TreeCheck Balanced →
  • 👉 Link here to the repo to solve the problem
  • 👌 Tips
  • 👊 Solution 1
Kodr
Content
IntroBig O NotationOptimisation
Coding Problems
Check PermutationIsUniqueURLify
Blogs
Tecnica Pomodoro
Social
About MeGitHub
Follow @diego_romero_x
Copyright © 2021 Kodr