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

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

9. 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

10. 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

11. 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

12. 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

13. 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

14. 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

15. CHALLENGE

Find in Shifted Sorted Matrix

Understanding the Matrix Shift Problem Suppose you have a matrix where each row and column is sorted in ascending order. Your task is to apply two specific types of shifts, described below, and locate a given element x in the transformed matrix. Shift Types Left Circular Shift (l): Definition: Moves the f...

Difficulty: 8/10 Mark Completed

16. CHALLENGE

Sum Nodes Within Range for a Binary Search Tree

A binary search tree is a data structure that has the following properties, Each node in the tree has only two children. The left subtree consists of nodes with values less than the root node. The right subtree consists of nodes with values greater than the root node. Consider that you are given a binary search tree as `ro...

Difficulty: 6/10 Mark Completed

17. CHALLENGE

Right Node View of Binary Tree

A binary search tree is a data structure that has the following properties, Each node in the tree has only two children. The left subtree consists of nodes with values less than the root node. The right subtree consists of nodes with values greater than the root node. Consider a binary tree with the root node given as `roo...

Difficulty: 6/10 Mark Completed

Cheat Sheet

• Quick summary: a kind of binary tree where nodes to the left are smaller, and nodes to the right are larger than the current node.
• Important facts:
  • Nodes of a binary search tree (BST) are ordered in a specific way:
    • All nodes to the left of the current node are smaller (or sometimes smaller or equal) than the current node.
    • All nodes to the right of the current node are larger than the current node.
  • Duplicate nodes are usually not allowed.
• Pros:
  • Balanced BSTs are moderately performant for all operations.
  • Since BST is sorted, reading its nodes in sorted order can be done in O(n), and search for a node closest to a value can be done in O(log(n))
• Cons:
  • Same as trees in general: no constant time operations, performance degradation in unbalanced trees.
• Time complexity (worst case):
  • Access: O(n)
  • Search: O(n)
  • Insertion: O(n)
  • Deletion: O(n)
• Time complexity (average case):
  • Access: O(log(n))
  • Search: O(log(n))
  • Insertion: O(log(n))
  • Deletion: O(log(n))
• See also:
  • An Intro to Binary Trees and Binary Search Trees
  • Interview Problems: Binary Search Trees