IT 279: Algorithms and Data Structures, Week 3 Trees recap

1. What are the height and depth of the J node in the tree above?

height = 1, Depth: 2

 

2. Which of the following is NOT a leaf node? D

 

3. Which of the following terms best describes the relationship of G to M? Aunt

 

 

HW 4. More Linked List Practice

void doUnion(const list<int>& list1, const list<int>& list2, list<int>& result)
{
    list<int>::const_iterator iter1;
    list<int>::const_iterator iter2;
    // your code here -- make sure to read the comment on the prototype before beginning work
    // Remember that you are expected to have an efficient solution: O(m+n), not O(m*n)

    iter1 = list1.begin();
    iter2 = list2.begin();


    while(iter1 != list1.end() && iter2 != list2.end()){
        if(*iter1 < *iter2){            // put smaller one first into the list
            result.push_back(*iter1);
            iter1++;
        }
        else if(*iter1 > *iter2){
            result.push_back(*iter2);
            iter2++;
        } else{
            result.push_back(*iter1);
            iter1++;
            iter2++;
        }
    }

    while(iter1 != list1.end()){
        result.push_back(*iter1);
        iter1++;
    }
    while(iter2 != list2.end()){
        result.push_back(*iter2);
        iter2++;
    }

}

void doIntersection(const list<int>& list1, const list<int>& list2, list<int>& result)
{
    list<int>::const_iterator iter1;
    list<int>::const_iterator iter2;

    // your code here -- make sure to read the comment on the prototype before beginning work
    // Remember that you are expected to have an efficient solution: O(m+n), not O(m*n)    
    // Note that an efficient answer to this is very closely related to an efficient answer to doUnion
    iter1 = list1.begin();
    iter2 = list2.begin();

    while(iter1 != list1.end() && iter2 != list2.end()){
        if(*iter1 < *iter2){
            iter1++;
        }
        else if(*iter1 > *iter2){
            iter2++;
        }
        else {
            result.push_back(*iter1);
            iter1++;
            iter2++;
        }
    }
}

 

 

 

Tree cannot be empty - always has at least one node.

Order of child nodes does not matter.

A tree with N nodes has N-1 edges.

 

 

Binary Search Tree

The Dictionary ADT

- unique keys

- insert, remove, find

Sorted dictionary implementation

We always insert a leaf

 

 

Binary Tree Notes:

Each non-empty node has exactly two subtrees

Binary tree may be empty

The subtrees are ordered

1-based height: h has at least h and most 2^h-1 elements in it

The height of a binary tree that contains n, n>0, elements is at most n and at least ceiling of log2(n+1).

 

Full binary tree vs complete binary tree

Full Binary Tree (or Strictly Binary Tree):

• Every node in the tree is either a leaf node or has exactly two children.
• This means there are no nodes with only one child.

Complete Binary Tree:

• All levels, except possibly the last, are completely filled.
• The last level has all its nodes on the left side.

root is index 1.(index 0, typically size of the tree)

node i's children are at indexes 2i and 2i+1

 

 

 

reference: geeksforgeeks.org

 

1. Inorder (Left, Root, Right) Traversal:
   • Process:
     1. Traverse the left subtree.
     2. Visit the root.
     3. Traverse the right subtree.
   • Usefulness:
     • For binary search trees (BSTs), an inorder traversal retrieves data in sorted order.
     • Used to convert a BST into a sorted linked list or array.
2. Preorder (Root, Left, Right) Traversal:
   • Process:
     1. Visit the root.
     2. Traverse the left subtree.
     3. Traverse the right subtree.
   • Usefulness:
     • Often used to create a copy of the tree.
     • Useful in prefix notation (Polish notation) of an expression.
     • Can be used to get a serialized form of a binary tree.
3. Postorder (Left, Right, Root) Traversal:
   • Process:
     1. Traverse the left subtree.
     2. Traverse the right subtree.
     3. Visit the root.
   • Usefulness:
     • Useful in postfix notation (Reverse Polish notation) of an expression.
     • Helps in deleting the tree. Delete children before the parent.
     • Used in algorithms to compute properties of nodes based on their descendants (like calculating the size of a subtree rooted at a node).
4. Level Order (or Breadth-First) Traversal:
   • Process:
     • Visit the root.
     • Traverse nodes at depth 1.
     • Traverse nodes at depth 2.
     • And so on...
   • Usefulness:
     • Useful to get a serialized form of a binary tree that preserves the structure without null placeholders.
     • Essential for algorithms that work level by level, like determining the minimum depth of a tree, or printing nodes at a given depth.
     • Commonly implemented using a queue.

// Inorder(LNR)
void inorder(TreeNode* root) {
    if (root == nullptr) return;
    inorder(root->left);
    cout << root->val << " ";
    inorder(root->right);
}

// Preorder(NLR)
void preorder(TreeNode* root) {
    if (root == nullptr) return;
    cout << root->val << " ";
    preorder(root->left);
    preorder(root->right);
}

// Postorder(LRN)
void postorder(TreeNode* root) {
    if (root == nullptr) return;
    postorder(root->left);
    postorder(root->right);
    cout << root->val << " ";
}