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