Send the link below via email or IMCopy
Present to your audienceStart remote presentation
- Invited audience members will follow you as you navigate and present
- People invited to a presentation do not need a Prezi account
- This link expires 10 minutes after you close the presentation
- A maximum of 30 users can follow your presentation
- Learn more about this feature in our knowledge base article
Do you really want to delete this prezi?
Neither you, nor the coeditors you shared it with will be able to recover it again.
Make your likes visible on Facebook?
You can change this under Settings & Account at any time.
Transcript of Trees
Buzz :Types of trees
Coding: Tree Traversals
Buzz: Tree traversal problems
More Tree Problems
Datastructure in which each node has 0 or more children recursively
Max child Count (K)
Depth: distance from root
Height: Max distance to leaf
Number of nodes in the sub-tree rooted at a given node
Most commonly k = 2 and we
call them binary trees
Height(lefttree) - Height(righttree)
For each type answer the following in O() notation
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
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?
Fill up each node of a tree with weight of the node's subtree
Given a tree, determine if it is a standard binary search tree.
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
In Order: ABCDEFGHI
Post Order: ACEDBHIGF
Level Traversal: FBGADICEH
Find inorder successor
Given a value, find its inorder successor in the tree.
Iterative version (assume you have a parent pointer)
Given 2 traversals of 3, construct the original tree. Is it always possible?
Assume that you have a stack datastructure, write iterative versions of the traversals.
Find Common Ancestor
Binary search 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