8. Trees

Binary search trees

0 of 5 activities0%

Reading 1

Ordered binary tree

Open

BST invariant: all keys in left subtree < node < all keys in right.

Search/insert average O(log n) if balanced; worst O(n) if skewed like a list.

Inorder traversal lists keys sorted.

TNode* search(TNode* t, int x){
  if(!t || t->val==x) return t;
  if(x < t->val) return search(t->left,x);
  return search(t->right,x);
}

Check 2

Open

A BST that inserts sorted keys with naive insert becomes

Fill in 3

Open

Try it 4

Open

Build 2-1-3.

main.cpp

Loading editor…

Program input (stdin)

Output will appear here.

Assignment 5

Open

Read n, n distinct ints inserted in order into a BST idea, then q. Print yes if q appears in the list (membership).

main.cpp

Loading editor…