Code 401 Class 15 Reading Notes

Tree

Common Terminology

• Node - A Tree node is a componenet which may contain its own values, and references to other nodes
• Root - The root is the node at the beginning of the tree
• K - A number that specifies the maximum number of a children any node may have in a k-ary tree.In a binary tree, k = 2.
• Left - A reference to one child node, in a binary tree
• Right - A reference to the other child node, in a binary tree
• Edge - The edge in a tree is the link between a parent and child node.
• Leaf - A leaf is a node that does not have any children.
• Height - The height of a trees is the number of edges from the root to the furthest leaf.

Traversals: Depth First and Breadth First

Depth first traversal: Going through the depth (height) of the tree first.

• Pre-order: __
• In-order: __
• Post-order: __

a) left » root » right

b) left » right » root

c) root » left » right

ALGORITHM preOrder(root)

  OUTPUT <-- root.value

  if root.left is not NULL
      preOrder(root.left) ## 

  if root.right is not NULL
      preOrder(root.right)

Things I want to know more about

How to return/print the top or left side of the binary tree.

<—BACK