Download the starter at the bottom of this page
- Construct a Binary Search Tree
- Search for data in a Binary Search Tree in logarithmic time
- Describe the properties and functionality of a Binary Tree
- Describe the properties and functionality of a Tree
- Traverse a Binary Tree in pre-order, in-order and post-order
- Traverse and Search a Tree in both Depth and Breadth-First order
- Solve coding challenges involving trees
Now that you've gotten a hang of tree traversal, lets try putting that knowledge to use. Be sure to inspect the test files and follow Polya's problem solving framework to understand the problems.
Starter file is located at tree-practice.js
Fill out findMinBST
and findMaxBST
which take in the RootNode of a binary
search tree and returns the min and max value respectively.
You should be able to solve this in O(log n) time.
Fill out findMinBT
and findMaxBT
which take in the RootNode of a binary
tree and returns the min and max value respectively.
How does this differ from finding the min value in a binary search tree? What is the time complexity of this operation?
Fill out getHeight
which takes the RootNode of a binary tree and returns
the tree's height. The height of a tree is the number of edges between the
RootNode and its furthest leaf.
Example:
Input:
1
/ \
2 3
/ \
4 5
Output: 2
Input:
1
/ \
null null
Output: 0
Input:
null
Output: -1
Given a binary tree, determine if it is height-balanced.
A height-balanced binary tree is defined as a binary tree in which the left and right subtrees differ in height by no more than 1, its left subtree is a balanced binary tree, and its right subtree is a balanced binary tree.
Example:
Input:
1
/
9
/
3
Output: False
Input:
1
/ \
9 20
/
3
Output: True.
Input:
1
/ \
9 20
/
3
/ \
5 6
Output: False
Input:
1
/ \
9 20
/ \ \
3 4 12
/ \
5 6
Output: True
Fill out countNodes
which takes the RootNode of a binary tree and returns
the number of Nodes contained in the tree.
Fill out getParentNode
which takes the RootNode of a binary tree and a
target value and returns the Node that points to the target value.
If the target cannot be found in the tree, getParentNode
should return
undefined
.
If the target is in the tree but has no parent, getParentNode
should return
null
.
Fill out inOrderPredecessor
which takes the RootNode of a binary tree and
a target value and returns the Node that comes before the target value in an
in-order traversal.
If the target is the first value in an in-order traversal, return null
.
target: 4
Input:
4
/ \
2 6
/ \ / \
1 3 5 7
Output: 3
Fill out inOrderPredecessor
which takes the RootNode of a binary tree and
a target, and deletes the target Node.
To delete a Node with no children, set its parent's pointer to null
.
To delete a Node with one child, replace it with it's child. This operation is similar to deleting a Node in a linked list.
To delete a Node with two children, replace the target Node's value with its in-order predecessor or successor, then delete the in-order predecessor or successor you used. You may need to do some additional research for details on this operation.
If the target value is not in the tree, return undefined
.
Example:
Input: Target: 5
Tree:
5
/ \
3 7
/ \ / \
2 4 6 8
Output:
4
/ \
3 7
/ / \
2 6 8
Or:
6
/ \
3 7
/ \ \
2 4 8
Fill out inOrderPredecessor which takes the RootNode of a binary tree and a target value and returns the Node that comes before the target value in an in-order traversal.
If the target is the first value in an in-order traversal, return null.
target: 4
Input:
4
/ \
2 6
/ \ / \
1 3 5 7
Output: 3
Delete Node in a Binary Search Tree Fill out inOrderPredecessor which takes the RootNode of a binary tree and a target, and deletes the target Node.
To delete a Node with no children, set its parent's pointer to null.
To delete a Node with one child, replace it with it's child. This operation is similar to deleting a Node in a linked list.
To delete a Node with two children, replace the target Node's value with its in-order predecessor or successor, then delete the in-order predecessor or successor you used. You may need to do some additional research for details on this operation.
If the target value is not in the tree, return undefined.
Example:
Input: Target: 5
Tree:
5
/ \
3 7
/ \ / \
2 4 6 8
Output:
4
/ \
3 7
/ / \
2 6 8
Or:
6
/ \
3 7
/ \ \
2 4 8
Fill out inOrderPredecessor which takes the RootNode of a binary tree and a target value and returns the Node that comes before the target value in an in-order traversal.
If the target is the first value in an in-order traversal, return null.
target: 4
Input:
4
/ \
2 6
/ \ / \
1 3 5 7
Output: 3
Delete Node in a Binary Search Tree Fill out inOrderPredecessor which takes the RootNode of a binary tree and a target, and deletes the target Node.
To delete a Node with no children, set its parent's pointer to null.
To delete a Node with one child, replace it with it's child. This operation is similar to deleting a Node in a linked list.
To delete a Node with two children, replace the target Node's value with its in-order predecessor or successor, then delete the in-order predecessor or successor you used. You may need to do some additional research for details on this operation.
If the target value is not in the tree, return undefined.
Example:
Input: Target: 5
Tree:
5
/ \
3 7
/ \ / \
2 4 6 8
Output:
4
/ \
3 7
/ / \
2 6 8
Or:
6
/ \
3 7
/ \ \
2 4 8