Trees

Notes

A tree is a data structure in which each node is comprised of some data as well as node pointers to child nodes.

We'll refer to node 1 as the root node, and external nodes like 5, 6, 7, 8, and 9 as leaves.

It's also convention to use the following terms to describe relationships between nodes:

  • nodes 2 and 3 are siblings of each other
  • nodes 5, 6, and 7 are children of node 3
  • node 2 is the parent of node 4

A binary tree is a type of tree in which each node is comprised of some data as well as node pointers to at most two children.

Here's an example of a binary tree node implementation.

Note how each node in a binary tree is comprised of two node pointers and some data.

n is the data stored in this node, and left and right are pointers either to the node's children (or to NULL if no children exist).

A binary search tree is a special type of binary tree that simplifies searching.

For each node in a binary search tree, every value on its left child's side is less than its own value, and every value on its right is greater. Notice how all values to the left of the root (55) are less than 55, and all the values to the right are greater than 55.

Here's some pseudocode to search a binary search tree for a particular value val.

If the current node's value is less than the value you're looking for, recursively search its right child. If the current node's value is greater than the value you're looking for, recursively search its left child.

Slides ( / )

study50 slide
study50 slide
study50 slide
study50 slide
study50 slide
study50 slide

Binary Tree Insertion

Implement a function with prototype

bool insert(int val)

that inserts a node containing val into the tree pointed to by the global root variable. Return true if successful, and return false if you failed for some reason (e.g., lack of sufficient heap memory, value already in tree, etc.).

jharvard@run.cs50.net (~): ../a.out
Inserting 0 ...success!
Inserting 1 ...success!
Inserting 2 ...success!
Inserting 3 ...fail!
Inserting 4 ...success!
Inserting 5 ...success!
Inserting 6 ...fail!
Inserting 7 ...fail!
Inserting 8 ...success!
Inserting 9 ...fail!
Tree contains 0? true
Tree contains 1? true
Tree contains 2? true
Tree contains 3? true
Tree contains 4? true
Tree contains 5? true
Tree contains 6? true
Tree contains 7? true
Tree contains 8? true
Tree contains 9? true

Try out some pseudocode here!
#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>

typedef struct node
{
    int n;
    struct node* left;
    struct node* right;
}
node;

node* root;

bool insert(int val)
{
    // TODO
}

bool search(node* root, int val)
{
    // if root is NULL
    if (root == NULL)
    {
        // return false
        return false;
    }		
    // if root->n is val	
    if (root->n == val)
    {
        // return true
        return true;
    }	
    // if val is less than root->n	
    else if (val < root->n)
    {
        // search left child
        return search(root->left, val);
	}	
    // if val is greater than root->n	
    else
    {
        // search right child
        return search(root->right, val);
    }
}

int main(void)
{
    // create root node
    root = malloc(sizeof(node));
    if (root == NULL)
    {
        printf("Out of memory!\n");
        return 1;
    }
    root->n = 7;
    root->left = NULL;
    root->right = NULL;
    
    // create more nodes
    node* three = malloc(sizeof(node));
    if (three == NULL)
    {
        printf("Out of memory!\n");
        return 1;
    }
    three->n = 3; 
    three->left = NULL;
    three->right = NULL;
    
    node* six = malloc(sizeof(node));
    if (six == NULL)
    {
        printf("Out of memory!\n");
        return 1;
    }
    six->n = 6;
    six->left = NULL;
    six->right = NULL;
    
    node* nine = malloc(sizeof(node));
    if (nine == NULL)
    {
        printf("Out of memory!\n");
        return 1;
    }
    nine->n = 9;
    nine->left = NULL;
    nine->right = NULL;

    // link together nodes
    root->left = three;
    root->right = nine;
    three->right = six; 
    
    // testing insert
    for(int i = 0; i < 10; i++)
    {
        printf("Inserting %i ...%s!\n", i, insert(i)? "success" : "fail");
    }
    for(int i = 0; i < 10; i++)
    {
        printf("Tree contains %i? %s\n", i, search(root, i)? "true" : "false");
    }
    
    return 0;
}

Videos

study50 video thumbnail

Wednesday, Week 6

An introduction to data structures
study50 video thumbnail

Bannus's Trees Short

Bannus gives a general overview