**Buzz: Trees Refresher**

Buzz :Types of trees

`

Coding: Tree Traversals

Buzz: Tree traversal problems

More Tree Problems

**Trees**

Datastructure in which each node has 0 or more children recursively

Max child Count (K)

Height/Depth

Weight

Balance

Relations/Tree properties

Depth: distance from root

Height: Max distance to leaf

Number of nodes in the sub-tree rooted at a given node

Root

Parent

Children

Ancestor

Internal node

Leaf node

Subtree

Most commonly k = 2 and we

call them binary trees

`

Height(lefttree) - Height(righttree)

For each type answer the following in O() notation

Max height/depth

Max value of balance

Max time for value lookup

Max Time taken to visit all nodes

Describe the trees that correspond to these values

Discuss each tree property in the context of the tree shown

Plain binary tree

Full binary tree

Complete binary tree

Perfect binary tree

Search tree

Balanced search tree

Order in which you visit nodes

visit represents action at a node (print, calculate a value, modify node etc)

For each traversal, write code for visit = print node

For each problem discuss and answer the following:

what traversal or traversals can use to solve this problem?

Function prototype

Visit function/code

Weights

Fill up each node of a tree with weight of the node's subtree

Is BST

Given a tree, determine if it is a standard binary search tree.

FreeTree

Delete all nodes of a given tree.

Fill balance values

Given a tree, fill up each of its nodes with the balance values (balance = height of left tree - height of right tree)

Find Max Degree

Find the max child count of a given binary tree (0 or 1 or 2)

Fill up depths

Given a tree, fill up each of its nodes with depth of that node.

Pre Order Traversal

In Order Traversal

Post Order Traversal

Level Traversal

PreOrder: FBADCEGIH

In Order: ABCDEFGHI

Post Order: ACEDBHIGF

Level Traversal: FBGADICEH

Find inorder successor

Given a value, find its inorder successor in the tree.

Recursive version

Iterative version (assume you have a parent pointer)

Construct tree

Given 2 traversals of 3, construct the original tree. Is it always possible?

Iterative traversals

Assume that you have a stack datastructure, write iterative versions of the traversals.

Find Common Ancestor

Binary search tree

Random tree

With parent pointer

Without parent pointer

Post fix and trees

Covert an expression tree to postfix

Convert a postfix string to an expression tree