Section Menu

How do I use this section?

1. LESSON

An Intro to Binary Trees and Binary Search Trees

Objective: In this lesson, we'll cover this concept, and focus on these outcomes: You'll learn what is a tree in general in the context of computer science. You'll learn what binary trees and binary search trees are. We'll show you how to use them in programming interview...

40 minutes Mark Completed

2. LESSON

BFS vs. DFS: Understanding Breadth First Search & Depth First Search

BFS vs. DFS Understanding Breadth First Search & Depth First Search Search During the days and weeks before a technical interview, we can apply the 80/20 rule for more efficient preparation. The 80/20 rule, otherwise known as Pareto's Law, stipulates that roughly 80% of your results will come from 20% of your efforts. Once you've gott...

52 minutes Mark Completed

3. LESSON

How Do We Get a Balanced Binary Tree?

The Marvel of Binary Trees: Understanding the Basics What is a Binary Tree? A Binary Tree is a specialized tree structure where each node has, at most, two child nodes. Interestingly, a binary tree can also be empty, meaning it has zero nodes. The Recursive Nature of Binary Trees One of the most intriguing aspects of binary tr...

41 minutes Mark Completed

4. LESSON

The Two Heaps Technique And Implementation

Objective: In this lesson, we'll cover this concept, and focus on these outcomes: You'll learn how to use the two heaps pattern when you need to find statistical values from a collection. We'll show you how to use this technique in programming interviews. You'll see how to ut...

42 minutes Mark Completed

5. LESSON

What Is A Segment Tree?

Welcome to the realm of Segment Trees! If you've meandered through the pathways of data structures, you've likely bumped into various trees. But today, we're introducing a special kind of tree that's less talked about yet incredibly powerful: the Segment Tree. What Exactly is a Segment Tree? Imagine you're building the next big thing sin...

47 minutes Mark Completed

6. LESSON

How Does the Minimax Algorithm Work?

Among the various components that are fundamental in Artificial Intelligence, algorithms are the most important ones. An algorithm basically is a sequence of unambiguous instructions that are used to solve a problem and conduct a sequence of specified actions. Artificial Intelligence is highly dependent on a couple of fundamental algorithms,...

27 minutes Mark Completed

7. LESSON

Huffman Coding Algorithm in Data Compression

The Huffman Coding Compression Algorithm Let's take a deep dive into the Huffman Coding Compression Algorithm and learn how to implement it step by step in various programming languages. Introduction...

42 minutes Mark Completed

8. CHALLENGE

Binary Tree Inorder Traversal

Can you write a function to traverse a binary tree in-order, and print out the value of each node as it passes? 4 \ 5 / 6 The example would output [4, 6, 5] since there is no left child for 4, and 6 is visited in-order before 5. <img src="https://storage.googleapis.com/algodailyrandomassets/cu...

Difficulty: 3/10 Mark Completed

9. CHALLENGE

Validate a BST

Given a binary search tree like the one below, can you write a function that will return true if it is valid? ` 5 / \ 3 9 / \ 1 4 ` Recall that a BST is val...

Difficulty: 4/10 Mark Completed

10. CHALLENGE

Bottom Left Node Value

Assume we're using a binary tree in writing a video game via Binary Space Partitioning. We need to identify the bottom left leaf, that is-- the leftmost value in the lowest row of the binary tree. <img src="https://...

Difficulty: 4/10 Mark Completed

11. CHALLENGE

Mean Per Level

We are given a binary tree and are tasked with writing a method that determines the average of every level in the tree. So for instance, given the following binary tree, we'd get [2, 5, 7] if the method grabbed the correct means. <img src="https://storage.googleapis.com/a...

Difficulty: 4/10 Mark Completed

12. CHALLENGE

Identical Trees

Can you write a function to see if two binary trees are identical? ` 1 1 / \ / \ 2 3 2 3 ` The above two trees share the same structure in terms of shape and location of each parent nodes' children. <img src="https://storage.googleapis.com/algodailyrandomassets/challenges/bstremoveleaf...

Difficulty: 4/10 Mark Completed

13. CHALLENGE

Max Per Level

Given a binary tree, write a method to return an array containing the largest (by value) node values at each level. In other words, we're looking for the max per level. So for instance, given the following binar...

Difficulty: 4/10 Mark Completed

14. CHALLENGE

String From Binary Tree

Suppose we're given a simple binary tree like the following: 1 / \ 2 3 \ 4 Can you generate a string based off the values of its nodes? <img src="https://storage.googleapis.com/algodailyrandomassets/curriculum/trees/str...

Difficulty: 5/10 Mark Completed

15. CHALLENGE

Merge Two Binary Trees

Merging Two Binary Trees The Problem Statement You are presented with two binary trees. Your task is to merge these trees into a single, new binary tree. Merging Binary Trees The Overlap Rule Here's the c...

Difficulty: 5/10 Mark Completed

16. CHALLENGE

Implement a Binary Search Tree

Let's implement a Binary Search Tree! Recall that a binary search tree, or a BST, is a binary tree that is ordered via these two properties: The left sub-tree of a node has a value less than or equal to its parent node's value. The right sub-tree of a node has a v...

Difficulty: 6/10 Mark Completed

17. CHALLENGE

How Deep Does It Go? Maximum Depth of Binary tree

Write a method to determine how deep a binary tree goes. The tree's depth can be described as the number of nodes you encounter as you traverse from the root node to a leaf. The root node is the topmost node, and a leaf is a node with no children. For example,...

Difficulty: 6/10 Mark Completed

18. CHALLENGE

Traverse in a Zig Zag

Here's a fun one: can you write a method to return the nodes of a binary tree in a zig zag level order? It should return a multi-dimensional array of...

Difficulty: 6/10 Mark Completed

19. CHALLENGE

Linked List to Binary Search Tree

We're given a sorted singly linked list (that is, a linked list made of nodes with no pointers to the previous node) where the elements are already arranged in ascending order. `js // -9 -> -2 -> 3 -> 5 -> 9 // Linked List Node Definition: function Node(val) { this.val = val; this.next = null; } ` Can you...

Difficulty: 7/10 Mark Completed

20. CHALLENGE

Is This Graph a Tree

Given an undirected graph, can you see if it's a tree? If so, return true and false otherwise. An undirected graph is a tree base...

Difficulty: 7/10 Mark Completed

21. CHALLENGE

Pick A Sign

We're given an array of positive integers like the following: `js [2, 1, 3, 2] ` Imagine that we're allowed to make each element of the array either a positive or negative number, indicated by a signage -- either a plus (+) or minus (-) sign that appears before it. If we sum up all the signed elements, we will get a tot...

Difficulty: 7/10 Mark Completed

22. CHALLENGE

Implement the Trie Data Structure

Suppose you're asked during an interview to design an autocompletion system. On the client side, you have an input box. When users start typing things into the input, it should parse what's been typed and ma...

Difficulty: 7/10 Mark Completed

23. CHALLENGE

Two Sum from BST

This problem is a fun combination of the famous Two Sum problem combined with a binary search tree. Given the root of a binary search tree, and a target integer K, return true if there exist two nodes in the said tree whose sum equals K. If no pai...

Difficulty: 7/10 Mark Completed

24. CHALLENGE

Lowest Common Ancestor

In the official React documentation, it's recommended that to find out where state data should live, the following steps be taken: Identify every component that renders something based on that state. Find a common owner component (a single component above all the components...

Difficulty: 7/10 Mark Completed

25. CHALLENGE

Sum Right Side Leaves

Finding the Sum of Right Leaves in a Binary Tree Imagine a family tree, but instead of tracking your relatives, it's tracking numbers. Each "person" in this tree has at most two "children," and some have none. We call these childless nodes "leaves," and your task is to find the sum of leaves that are on the right side of their...

Difficulty: 7/10 Mark Completed

26. CHALLENGE

Invert a Binary Tree

Can you invert a binary tree over its vertical axis? This is a famous problem made popular by this tweet: Google: 90% of our engineers use the software you wrote (Homebrew), but you can’t invert a binary tree on a whiteboard so f**k off.&mdash; Max Howell (@mxcl) <a href="https://twitter.co...

Difficulty: 7/10 Mark Completed

27. CHALLENGE

Serialize and Deserialize a Binary Tree

Given a binary tree representation, can you come up with a method to serialize the tree and then deserialize it to get the exact same tree? What is Serialization and Deserialization? Serializat...

Difficulty: 8/10 Mark Completed

28. CHALLENGE

Climbing the Word Ladder

Imagine two words placed at the two ends of a ladder. Can you reach one word from another using intermediate words as rings of the ladder? Each successive or transition word has a difference of only one letter from its predecessor, and must belong to a provided dictionary. Can we achieve this using the shortest possible number of r...

Difficulty: 7/10 Mark Completed

29. CHALLENGE

Get Binary Tree Leaves

Suppose we're given a binary tree, one with several leaves like such: We're asked to get all the current leaf values, then delete the leaves. Then we repeat-- we again get the leaf values, and then delete-- proceeding un...

Difficulty: 6/10 Mark Completed

30. CHALLENGE

Counting Univalued Subtrees

Question Can you count all the univalued subtrees in a binary tree, as shown in the figure below? The Problem We are given a binary tree. The challenge is to count all the univalued subtrees in the tree. Just to recall, a subtree is any node along with its...

Difficulty: 6/10 Mark Completed

Cheat Sheet

• Quick summary: a data structure that stores a hierarchy of values.
• Important facts:
  • Organizes values hierarchically.
  • A tree item is called a node, and every node is connected to 0 or more child nodes using links.
  • A tree is a kind of graph where between any two nodes, there is only one possible path.
  • The top node in a tree that has no parent nodes is called the root.
  • Nodes that have no children are called leaves.
  • The number of links from the root to a node is called that node's depth.
  • The height of a tree is the number of links from its root to the furthest leaf.
  • In a binary tree, nodes cannot have more than two children.
    • Any node can have one left and one right child node.
    • Used to make binary search trees.
    • In an unbalanced binary tree, there is a significant difference in height between subtrees.
    • An completely one-sided tree is called a degenerate tree and becomes equivalent to a linked list.
  • Trees (and graphs in general) can be traversed in several ways:
    • Breadth first search (BFS): nodes one link away from the root are visited first, then nodes two links away, etc. BFS finds the shortest path between the starting node and any other reachable node.
    • Depth first search (DFS): nodes are visited as deep as possible down the leftmost path, then by the next path to the right, etc. This method is less memory intensive than BFS. It comes in several flavors, including:
      • Pre order traversal (similar to DFS): after the current node, the left subtree is visited, then the right subtree.
      • In order traversal: the left subtree is visited first, then the current node, then the right subtree.
      • Post order traversal. the left subtree is visited first, then the right subtree, and finally the current node.
• Pros:
  • For most operations, the average time complexity is O(log(n)), which enables solid scalability. Worst time complexity varies between O(log(n)) and O(n).
• Cons:
  • Performance degrades as trees lose balance, and re-balancing requires effort.
  • No constant time operations: trees are moderately fast at everything they do.
• Notable uses:
  • File systems.
  • Database indexing.
  • Syntax trees.
  • Comment threads.
• Time complexity: varies for different kinds of trees.
• See also:
  • Interview Problems: Trees