Advanced Binary Tree Case Studies and Traversal Algorithms
Explore in-depth case studies of binary trees, including DFS and BFS problems. Learn about tree traversal algorithms and solving tree-related challenges such as node values, tree inclusion, sum, min value, and maximum path sum.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
You are allowed to download the files provided on this website for personal or commercial use, subject to the condition that they are used lawfully. All files are the property of their respective owners.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.
E N D
Presentation Transcript
Topics covered Binary trees case studies: Depth first values problem Depth First Search (DFS) Breadth first values problem Breadth First Search (BFS) Tree includes problem Tree sum problem Tree min problem Max path sum problem Binary tree traversal algorithms Full/complete binary trees
Binary tree case study 1: depth first values Depth first traversal of binary tree Storing elements in an array list A This results in following list A, B, D, E, C, F B C D E F Solutions Iterative solution: Stack-based Recursive solution
Binary tree case study 2: breadth first values Breadth first traversal (level-order traversal) of binary tree Storing elements in an array list A B C This results in following list A, B, C, D, E, F D E F Solution Iterative solution: Queue-based
Binary tree case study 3: tree includes A Objective Find a target node value in the tree B C This results in True if value is found in tree False, otherwise D E F Solution Recursive traversal-based solution
Binary tree case study 4: tree sum Objective Find total sum of values in binary tree 3 11 4 This results in 25 For tree given on right-hand side 4 2 1 Solution Recursive traversal-based solution
Binary tree case study 5: tree min Objective Find minimum value in binary tree 3 11 4 This results in 1 For tree given on right-hand side 4 2 1 Solution Recursive traversal-based solution
Binary tree case study 6: max path sum Objective Find maximum path sum 3 11 4 This results in 18 For tree given on right-hand side 4 2 1 Solution Recursive traversal-based solution
Binary tree traversal Processing all the nodes by visiting each individual node exactly once Pre-order (VLR) V Post-order (LRV) In-order traversal (LVR) L R
Pre-order traversal In a pre-order traversal a node is visited before its left subtree And before its right subtree AlgorithmPreOrder(T,v) visit(v) ifT.hasLeft(v) PreOrder(T, T.left(v)) ifT.isRight(v) PreOrder(T, T.Right(v))
Post-order traversal In a post-order traversal a node is visited after its left subtree And after its right subtree AlgorithmPostOrder(T,v) ifT.hasLeft(v) PostOrder(T,T.left(v)) ifT.hasRight(v) PostOrder(T,T.right(v)) visit(v)
In-order traversal In an in-order traversal a node is visited after its left subtree And before its right subtree AlgorithmInOrder(T,v) ifT.hasLeft(v) InOrder(T,T.left(v)) visit(v) ifT.hasRight(v) InOrder(T,T.right(v))
Full binary tree Full binary tree of height k Binary tree of depth k having 2k+1 -1 nodes Only nodes at depth k are leaves and all the internal nodes have two children You can number nodes in the tree Root 1 Nodes at any level are numbered from left to right Parent of node i is numbered floor(i/2) Left child of i is numbered 2i Right child of i is numbered 2i+1 1 2 3 4 5 6 7
Complete binary tree A complete binary tree of height k with n nodes Its nodes corresponds to the nodes numbered one to n in the full binary tree of height k 1 1 1 2 3 2 3 2 3 4 5 6 7 4 5 4 5 7 FULL/COMPLETE NOT COMPLETE COMPLETE
More properties for binary trees For a proper binary tree: nb of external nodes = nb of internal nodes + 1 The height of a full binary tree with n nodes is log2(n+1)-1 The height of a complete binary tree with n nodes is log2(n+1)-1 <= h < log2(n+1)
