Loading presentation...

Present Remotely

Send the link below via email or IM

Copy

Present to your audience

Start 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.

DeleteCancel

Make your likes visible on Facebook?

Connect your Facebook account to Prezi and let your likes appear on your timeline.
You can change this under Settings & Account at any time.

No, thanks

Trees

No description
by

Kalyan Sonnathi

on 2 June 2015

Comments (0)

Please log in to add your comment.

Report abuse

Transcript of Trees

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
Full transcript