Unit 2

Two contexts in which using a Tree may be helpful are:

1. File systems in your computer.
2. Family trees of origin in real life.

1. 9
2. Node 9's parent
3. Node 9’s children
4. Root
5. Leaves

1. Subtrees
2. The blue root is node 2. The red root is node 9
3. Node 6 and node 1
4. Leaf nodes are nodes that have no children, and in this tree we have 3, 7, 2 and 1.

A binary tree is a tree that must satisfy the condition of having at most 2 children per node.

In the context of representing a sports tournament bracket as a tree:

• The root would represent the team that won the entire tournament.
• The leaves would represent all of the teams that competed in this tournament.

Solution:

The one on the right is not a BST. Notice that it breaks the ordering invariant, there are numbers on the left of 1 that are greater than 1, however, a BST requires that for any parent node, all the nodes on its left must be less than and all its nodes on the right must be greater than the value of the parent node. On the right of the tree, there are two 9s, which is also not allowed in a BST. We cannot have duplicate values.
The one on the left is a valid BST.

Solution:

• The root: S
• Children of node X: A and R
• Parent of node X: T
• Leaves: A, R, H

This is a binary tree because each tree has at most 2 children.

Only the odd values of thre tree in a list: [27, 1, 9, 29, 47]

This function will return a list of the elements of the given tree in left-to-right order, where each element of the list is the original value in the tree squared. In essence, this function traverses the binary tree recursively and constructs a list containing the squares of the values associated with each node.

def printValues(T):
   if T == None:
       return
   else:
       # Recursive print everything to the left of the current node
       printValues(T["left"])

       # Print the current node
       print(T["contents"])

       # Recursive print everything to the right of the current node
       printValues(T["right"])
        

t = { "contents": 5,
       "left": {
           "contents": 3,
           "left": {
               "contents": 1,
               "left": None,
               "right": None
           },
           "right": {
               "contents": 4,
               "left": None,
               "right": None
           }
       },
       "right": {
           "contents": 13,
           "left": {
               "contents": 7,
               "left": None,
               "right": None
           },
           "right": {
               "contents": 15,
               "left": None,
               "right": None
           }
       }
   }
        

def findMax(T):
   if T == None:
       return -1
   else:
       current = T["contents"]
       leftMax = findMax(T["left"])
       rightMax = findMax(T["right"])
       return max(current, leftMax, rightMax) # returns the largest of the three
            
        

def findChildren(T, node):
   if T == None:
       return []
   else:
       # Check if we have reached the desired node
       if T["contents"] == node:
           children = []
           # Add any existing children to the list
           if T["left"] != None:
               children.append(T["left"]["contents"])
           if T["right"] != None:
               children.append(T["right"]["contents"])
           return children
       else:
           # Recursively search for the node to the left and right of the current node
           leftChildren = findChildren(T["left"], node)
           rightChildren = findChildren(T["right"], node)
           return leftChildren + rightChildren

            

        

def countNodes(t): 
    if t == None: 
        return 0 
    else: 
        count = 0 
        count += countNodes(t["left"]) 
        count += countNodes(t["right"]) 
        return count + 1

        

def sumNodes(t): 
    if t == None: 
        return 0
    else: 
        result = sumNodes(t["left"]) + sumNodes(t["right"]) 
        return result + t["contents"]

        

def listValues(t): 
    if t == None: 
        return []
    else: 
        return listValues(t["left"]) + [t["contents"]] + listValues(t["right"])

        

def findBSTMax(t): 
    if t["right"] == None: 
        return t["contents"]
    else: 
        return findBSTMax(t["right"])
        

def findBSTMin(t): 
    if t["left"] == None: 
        return t["contents"]t
    else: 
        return findBSTMin(t["left"])