Introduction to binary search trees (BSTs)

On this page

Introduction to binary search trees (BST)
Questions

This lesson contains approximately 15 minutes of video content.

Introduction to binary search trees (BST)

Correction: In this video, we show struct BinaryTreeNode<T1,T2> with pointer data members typed Node<T1,T2>*. Those pointers (i.e., parent, left, and right) should have been typed BinaryTreeNode<T1,T2>*.

Questions

QBST Intro, Q1

This question is ungraded.

The nodes of a binary search tree are arranged to satisfy the binary-search-tree property. In this lesson, we define that property such that,

Let x be a node in the BST,
If y is a node in the left subtree of x,
then

`y.key != x.key`

`y.key < x.key`

`y.key == x.key`

`y.key >= x.key`

Practice question: try as many times as you like

QBST Intro, Q2

This question is ungraded.

The nodes of a binary search tree are arranged to satisfy the binary-search-tree property. In this lesson, we define that property such that,

Let x be a node in the BST,
If y is a node in the right subtree of x,
then

`y.key != x.key`

`y.key < x.key`

`y.key == x.key`

`y.key >= x.key`

Practice question: try as many times as you like

QBST Intro, Q3

This question is ungraded.

What is the height of the following binary search tree?

Practice question: try as many times as you like

QBST Intro, Q4

This question is ungraded.

What is the depth of the node with the value 23 in following binary search tree?

Practice question: try as many times as you like