Binary Search Tree

Task 1 Is it a binary search tree?

Suppose that a binary search tree stores numbers between 1 and 1000, and we are searching for from it. Which of the following sequences is not possible to be the sequence of nodes visited during the search process?

Where is the mistake? The (first) wrong value is:

Task 2 Build binary search tree

Fill in the template to demonstrate how to build a binary search tree by using InsertNode function.

function InsertNode (tree, newNode) {
  y = NaN
  x = tree.root
  while x != NaN {
      y = x
      if (newNode.key < x.key) {
        x = x.left
      }
      else {
        x = x.right
      }
  }
  newNode.parent=y
  if (y == NaN) {
    tree.root=newNode
  }
  elseif (newNode.key < y.key) {
    y.left=newNode
  }
  else { 
    y.right=newNode
  }
}

Input array is . Use its first element as the root of a tree, and then insert the rest elements into this tree.

Click on a node;
Fill in expected value;
Press enter key, or use the floating add button to add children for leaves.

Task 3 Build red-black tree

Fill in the following templates to demonstrate how to build a red-black Tree by using InsertNodeRB function.

function InsertNodeRB(tree, newNode) {
  y=tree.nil
  x=tree.root
  while x!=tree.nil {
    y=x
    if (newNode.key < x.key) {
      x=x.left
    }
    else {
      x=x.right
    }
  }
  newNode.parent=y
  if (y==tree.nil) { 
    tree.root=newNode
  }
  elseif (newNode.key < y.key) {
    y.left=newNode
  }
  else { 
    y.right=newNode
  }
  newNode.left=tree.nil 
  newNode.right=tree.nil 
  newNode.color=red 
  FixRB(tree,newNode)
}

function FixRB(tree,newNode) {
  while newNode.parent.color==red {
    if (newNode.parent==newNode.parent.parent.left) {
      y=newNode.parent.parent.right
      if (y.color==red) {
        newNode.parent.color=black 
        y.color=black 
        newNode.parent.parent.color=red 
        newNode=newNode.parent.parent 
      }
      else {
        if (newNode==newNode.parent.right) {
            newNode=newNode.parent 
            LeftRotate(tree,newNode)
        }
        newNode.parent.color=black 
        newNode.parent.parent.color=red 
        RightRotate(tree, newNode.parent.parent)
      }
    }
    else {
      same logic but with "right" and "left" exhanged
    }
  }
  tree.root.color=black
}

Input array is . Use its first element as the root of a tree, and then insert the rest elements into this tree.

Click on a node;
Fill in expected value;
Press enter key, or use the floating plus button to add children for leaves.
Use the red (R) and blac (B) buttons to color the nodes.