Trees + Tree Traversal

Question 1

What is a tree?

Answer 1

• Symbol = T
• Undirected graph
• No Cycles but connected
• Used to represent or break down a range of problems or concepts

Question 2

How can you determine a tree structure?

Answer 2

1. Each pair of verticies (u and v), one path from U to V
   
   1. That does not repeat any edges of vertices
2. Additional edges between any vertices will produce a cycle
3. Removing any edge produces a disconnected graph

Question 3

What are rooted trees?

Answer 3

• Common type of tree
• One vertex (point) is specified as a root
• Root usually at top of tree
• Therefore a tree with n vertices will have n-1 edges

Question 4

Give the structure of a tree

Answer 4

Question 5

What are binary trees?

Answer 5

• Rooted Tree
• In which every parent has at most two children
  
  • Child can be left or right
  • Every parent has at most one left and right child
• FULL BINARY TREE each parent has two children
  
  • Total Vertices = 2n + 1 (n is internal vertices)
• Full m-ary tree - each parent has m children
  
  • Total Vertices = mn + 1 (n is internal vertices)

Question 6

What are the calculations for a FULL binary tree

Answer 6

Question 7

What are the calculations for a m-ary tree

Answer 7

Total Vertices = mn + 1 (n is internal vertices)

Question 8

What is the importance of Binary Trees

Answer 8

• Used to represent a mathematical or logical equation
• Internal vertices are arithmetic operators
• Leaves are variables
• Can calculate using left to right

Question 9

What is preorder traversal

Answer 9

Question 10

What is inorder traversal?

Answer 10

Question 11

What is Postorder Traversal

Answer 11