Trees Conceptual Review

What is a Tree?

A node-based data structure with nodes arranged in parent-child relationships.

How do trees usually grow?

Trees grow downwards, like a pyramid.

How many parents can a child node have?

Only one.

Can a parent node have multiple child nodes, or just one?

It can have multiple child nodes.

What is a binary tree?

A tree where each parent node can only have 2 child nodes at most.

What direction(s) do we move in a binary tree?

Left or Right.

What is the root?

The topmost node of a tree.

What’s a leaf node?

A node with no child nodes.

What is an edge?

A pointer that connects 2 nodes.

What is a branch?

Refers to the path we take to get from the root node to a specified node.

What are Siblings?

Child nodes that share the same parent.

• What is a subtree?

• What nodes can form subtrees?

• A smaller tree within a larger tree.

• Any parent-child node group can form a subtree.

What are the ‘ancestors’ of a node?

The nodes that come before a specified node on a branch.

What are the ‘descendants’ of a node?

All the nodes that branch out from the specified node.

What is an internal node?

Any node in a tree that has at least one child.

What is the degree of a node?

How many child nodes a node has.

What is height?

How far up a node is on a Tree.

What is Depth?

How far down a node is in a Tree.

What can we use to count the Height and/or Depth of a node?

Edges.

What is a Binary Search Tree? Think about a specific rule that separates a BST from a standard Binary Tree.

Its a type of Binary Tree where nodes to the left of the parent/root node are less than the parent/root node while nodes on the right are greater than the parent/root node.

What 2 rules should you follow in a BST when adding/finding nodes?

• Move to the left of a BST if the node you’re looking for is less than the current parent node or root node.

• Move to the right of a BST if the node you’re looking for is greater than the current parent node or root node.

How do you add a node to a BST? Describe the process with as much detail as possible.

• Start from the root and follow the rules of traversal for adding/inserting nodes.

• If the node you want to add is less than the current parent node, then add the node to the left of the parent node as a child node.

• But, you should make sure that the node you’re adding is only added as a leaf node.

How do you remove a node to a BST? Describe the process with as much detail as possible (hint: there’s 3 scenarios to this!)

• If you need to delete a leaf node:

  • Simply delete the edge connecting the leaf node with its parent node.

• Delete a node with one child:

  • Connect the child node with the next predecessive parent node to “replace” the node you wish to delete with the child.

• Delete a node with 2 children:

  • Look for a node with the next highest value from the node you wish to delete’s value.

  • Once you get that node, replace the node you wish to delete with that node.

  • If the node you’re using to replace has a child node, connect it with the predecessive parent node.

Does a Binary Search Tree allow for duplicates?

No, they do not.

What’s a Self-Balancing Binary Search Tree?

A special type of BST that has an algorithm where branches are automatically kept close to the same length.

Classify these Tree Types in the right order:

• Binary Search Tree

• Tree

• Binary Tree

• Self-Balancing Binary Search Tree

• Node-based Data Structure

(it should go from broad to specific)

(most broad) Node-Based Data Structure → Tree → Binary Tree → Binary Search Tree → Self Balancing Binary Search Tree (most specific)

How do you print nodes in Pre-Order Traversal?

Start by printing the root node, then the left node, then the right node (root →  left → right).

How do you print nodes in In-Order Traversal?

Start by printing the left node, then the root node, and then finally the right node.

How do you print nodes in Post-Order Traversal?

Start by printing the left node, then the right node, and then finally the root node.

For what use-case would you use Pre-Order Traversal for?

If you want to make a duplicate of your tree.

For what use-case would you use In-Order Traversal for?

List the nodes of the tree in order.

For what use-case would you use Post-Order Traversal for?

When you want to delete leaf nodes from a tree.

• What operations are Trees efficient at?

• What operations are Trees slow at?

• Ordered node search & retrieval.

• Input and retrieval in general.