Tree

Tree

2

The first node in a tree is called the?

Tree

4

A link connecting one node to another is called an?

edge

4

A node can only have _____?

one parent node

5

What is the relationship between node B and nodes E and F?

Node E is B's  ____ child node, and node F is B's ___ child node.

left child node, right child node

5

What are nodes C, D, E, and G called?

Leaf nodes or Leaves

Pre-order Traversal

2

Pre-order Traversal is a type of Depth First Search, where each ____ is visited in a certain order.

node

4

This traversal is "pre" order because the node is visited "____" the recursive pre-order traversal of the left and right subtrees.

before

4

Pre-order Traversal is a type of _____? 

Depth First Search

5

Pre-order Traversal is done by visiting the ____ node first.

root

5

_{Given the illustration below, what do you think is the missing code?}

_{class TreeNode:}

    _{def __init__(self, data):}

        _{self.data = data}

        _{self.left = None}

        _{self.right = None}

_{def _________(node):}

    _{if node is None:}

        _return

    _{print(node.data, end=", ")}

    _{preOrderTraversal(node.left)}

    _{preOrderTraversal(node.right)}

_{root = TreeNode('R')}

_{nodeA = TreeNode('A')}

_{nodeB = TreeNode('B')}

_{nodeC = TreeNode('C')}

_{nodeD = TreeNode('D')}

_{nodeE = TreeNode('E')}

_{nodeF = TreeNode('F')}

_{nodeG = TreeNode('G')}

_{root.left = nodeA}

_{root.right = nodeB}

_{nodeA.left = nodeC}

_{nodeA.right = nodeD}

_{nodeB.left = nodeE}

_{nodeB.right = nodeF}

_{nodeF.left = nodeG}

_{preOrderTraversal(root)}

_{preOrderTraversal}

In-order Traversal

2

In-order Traversal is a type of ____ Search?

Depth First Search,

4

This traversal is mainly used for Binary Search Trees where it returns values in ascending order.

In-order Traversal

4

_______ does a recursive In-order Traversal of the left subtree.

In-order Traversal

5

Given the code below, what do you think is the missing in line of codes?

class TreeNode:

    def __init__(self, data):

        self.data = data

        self.left = None

        self.right = None

def _______ (node):

    if node is None:

        return

    inOrderTraversal(node.left)

    print(node.data, end=", ")

    inOrderTraversal(node.right)

root = TreeNode('R')

nodeA = TreeNode('A')

nodeB = TreeNode('B')

nodeC = TreeNode('C')

nodeD = TreeNode('D')

nodeE = TreeNode('E')

nodeF = TreeNode('F')

nodeG = TreeNode('G')

root.left = nodeA

root.right = nodeB

nodeA.left = nodeC

nodeA.right = nodeD

nodeB.left = nodeE

nodeB.right = nodeF

nodeF.left = nodeG

inOrderTraversal(root)

inOrderTraversal

5

Given the code below, what do you think is the missing in line of codes?

class TreeNode:

        self.data = data

        self.left = None

        self.right = None

def inOrderTraversal(node):

    if node is None:

        return

    inOrderTraversal(node.left)

    print(node.data, end=", ")

    inOrderTraversal(node.right)

root = TreeNode('R')

nodeA = TreeNode('A')

nodeB = TreeNode('B')

nodeC = TreeNode('C')

nodeD = TreeNode('D')

nodeE = TreeNode('E')

nodeF = TreeNode('F')

nodeG = TreeNode('G')

root.left = nodeA

root.right = nodeB

nodeA.left = nodeC

nodeA.right = nodeD

nodeB.left = nodeE

nodeB.right = nodeF

nodeF.left = nodeG

inOrderTraversal(root)

def __init__(self, data):

Post-Order Traversal

2

What makes this traversal "post" is that visiting a node is done "_____" the left and right child nodes are called recursively.

after

4

Given the code below, what do you think is the missing in line of codes?

class TreeNode:

    def __init__(self, data):

        self.data = data

        self.left = None

        self.right = None

def ______ (node):

    if node is None:

        return

    postOrderTraversal(node.left)

    postOrderTraversal(node.right)

    print(node.data, end=", ")

root = TreeNode('R')

nodeA = TreeNode('A')

nodeB = TreeNode('B')

nodeC = TreeNode('C')

nodeD = TreeNode('D')

nodeE = TreeNode('E')

nodeF = TreeNode('F')

nodeG = TreeNode('G')

root.left = nodeA

root.right = nodeB

nodeA.left = nodeC

nodeA.right = nodeD

nodeB.left = nodeE

nodeB.right = nodeF

nodeF.left = nodeG

# Traverse

postOrderTraversal(root)

#Python

postOrderTraversal

4

Given the code below, what do you think is the missing in line of codes?

class TreeNode:

    def __init__(self, data):

        self.data = data

        self.left = None

        self.right = None

def postOrderTraversal(node):

    if node is None:

        return

    postOrderTraversal(node.left)

    postOrderTraversal(node.right)

___________

root = TreeNode('R')

nodeA = TreeNode('A')

nodeB = TreeNode('B')

nodeC = TreeNode('C')

nodeD = TreeNode('D')

nodeE = TreeNode('E')

nodeF = TreeNode('F')

nodeG = TreeNode('G')

root.left = nodeA

root.right = nodeB

nodeA.left = nodeC

nodeA.right = nodeD

nodeB.left = nodeE

nodeB.right = nodeF

nodeF.left = nodeG

# Traverse

postOrderTraversal(root)

#Python

 print(node.data, end=", ")

5

It is used for deleting a tree, post-fix notation of an expression tree, etc.

Post-order Traversal

5

Given the code below, what do you think is the missing in line of codes?

class TreeNode:

    def __init__(self, data):

        self.data = data

        self.left = None

        self.right = None

def postOrderTraversal(node):

    if node is None:

        return

    postOrderTraversal(node.left)

    postOrderTraversal(node.right)

    print(node.data, end=", ")

nodeA = TreeNode('A')

nodeB = TreeNode('B')

nodeC = TreeNode('C')

nodeD = TreeNode('D')

nodeE = TreeNode('E')

nodeF = TreeNode('F')

nodeG = TreeNode('G')

root.left = nodeA

root.right = nodeB

nodeA.left = nodeC

nodeA.right = nodeD

nodeB.left = nodeE

nodeB.right = nodeF

nodeF.left = nodeG

# Traverse

postOrderTraversal(root)

#Python

root = TreeNode('R')

Binary Search Tree

2

A _______ is a Binary Tree where every node's left child has a lower value, and every node's right child has a higher value.

 Binary Search Tree

4

The ____ of a tree is the number of nodes in it (n�).

size

4

The descendants of a node are all the _____ of that node, and all their child nodes, and so on.

child nodes

5

The node's ____ is the maximum number of edges between that node and a leaf node.

height

5

A _____ starts with one of the nodes in the tree as a local root, and consists of that node and all its descendants.

subtree