Binary Trees

Question 1

What are ancestor nodes?

Answer 1

nodes that are between the current node and the root node, including the root node

Question 2

What is the root node?

Answer 2

the very first node of the tree?

Question 3

What is a grandparent node?

Answer 3

the parent node of the parent node of the current node

Question 4

What are leaf nodes?

Answer 4

nodes without any children

Question 5

What is a binary tree?

Answer 5

a data structure made up of nodes, where each node has at most two children nodes

Question 6

How do you calculate the depth of a node?

Answer 6

The amount of parent nodes between the current node and the root node, including the current node

Question 7

What is the height of a tree?

Answer 7

the height of its root node. the amount of its children node layers.

Question 8

What is a complete binary tree?

Answer 8

every level except possible the last, is completely filled and all the nodes in the last level are as far left as possible

Question 9

What is a full binary tree?

Answer 9

a tree in which every nodes has either 0 or 2 children

Question 10

How do we implement a Binary Tree?

Answer 10

We create a class Node. The Node class will have three attributes: value, left, right. We create a class BinaryTree. WIthin the BinaryTree class, we use the Node class to create new nodes in our binary tree

Question 11

Tree traversal

Answer 11

is the process of visiting each node in the tree data structure exactly once. There are multiple ways to traverse a free: depth-first or breadth-first order.

Question 12

What are the Three ways to traverse a tree in depth-first oder?

Answer 12

In-order, pre-order, post-order

Question 13

Explain pre-order depth-first tree traversal

Answer 13

follows the order: Root -> Left -> Right

checks if the current node is empty, displays the value of the current node, recursively calls the pre-order function on the left subtree, then recursively calls the pre-order function of the right subtree

Question 14

Explain in-order depth-first

Answer 14

similar to pre-order depth-first, except it follows the order of: Left -> Root -> Right

make recursive call to the left child, concat the value of the current node with traversal, make a recursive call to the right subtree

Question 15

Explain post-order depth-first

Answer 15

make recursive call to the left subtree and the right subtree before concatenating the value of the current node with traversal

Question 16

Explain level-order breadth-first

Answer 16

we leverage a queue. We enqueue the root node. We dequeue from the queue and add it to the Traversal. We enqueue the children of the node we dequeued. We dequeue first node in the queue. Add it to the Traversal. And enqueue its children. And we repeat

Question 17

Explain reverse level-order traversal

Answer 17

we leverage a queue and a stack. It’s similar to the level-order except we enqueue the right child before the left child. And after we dequeue the node from the queue we push it onto the stack. After, we check if the node has children, if so we enqueue the children. We repeat this process until the queue becomes empty. At which point, we pop the elements from the stack, appending to the traversal string to achieve the reversed result

Question 18

Calculate the height of a tree

Answer 18

break down the problem using recursion and traverse thru the left and right subtree of a node to calculate the height of that node. Calculate the max of the two heights and add one to get the height of the tree