Binary Trees and Tree Traversals
Delve into the world of binary trees, exploring their structure, definitions, and implementations. Learn about in-order, pre-order, and post-order traversals, along with techniques for printing tree contents. Understand the significance of nodes and hierarchies in computer science, and explore the diverse applications of trees in various domains like natural language processing and file representation. Strengthen your knowledge of trees with lessons from Summer 2023 sessions.
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
Binary Trees Hitesh Boinpally Summer 2023
Agenda Binary Trees Traversals Reminders Lesson 9 - Summer 2023 2
Agenda Binary Trees Traversals Reminders Lesson 9 - Summer 2023 3
Trees in Computer Science Lesson 9 - Summer 2023 4
Trees in Computer Science Implementation for TreeMap / TreeSet Decision Trees How files / folders are represented Family Trees, Org Charts Parse trees a = (b + c) * d Natural language processing Lesson 9 - Summer 2023 5
Trees Defined Tree: Nodes linked together in some hierarchical fashion Binary Tree: A tree where each node has at most 2 children Recursive Definition: A tree is either: 1. Empty 2. A node with data, and a left and right subtree Lesson 9 - Summer 2023 6
Trees Defined root Tree: Nodes linked together in some hierarchical fashion Binary Tree: A tree where each node has at most 2 children 1 2 3 Recursive Definition: A tree is either: 1. Empty 2. A node with data, and a left and right subtree 4 5 6 Lesson 9 - Summer 2023 7
Trees Defined A tree is either: 1. 2. Empty A node with data, and a left and right subtree root root root root root 1 1 12 -1 2 3 2 13 9 4 5 6 4 Lesson 9 - Summer 2023 8
Printing Trees root Want to print out the contents of the tree Our intended output: 48 48 21 5 10 8 6 21 10 5 8 6 Lesson 9 - Summer 2023 9
Printing Trees root Want to print out the contents of the tree 48 Different ways to do so: 21 10 Pre-order 48 21 5 10 8 6 In-order 5 21 48 8 10 6 5 8 6 Post-order 5 21 8 6 10 48 Lesson 9 - Summer 2023 11
Whats the in-order traversal of this tree? slido.com code: #su_cse123 root 12 16 10 5 23 6 8 4 42 Lesson 9 - Summer 2023 12
Whats the in-order traversal of this tree? slido.com code: #su_cse123 root 12 16 10 5 23 6 Answer: 5 4 16 12 42 23 10 6 8 8 4 42 Lesson 9 - Summer 2023 13
Practice: pathSum root Given a number, print out all sums that have value greater than or equal to the given number for a tree in a pre-order fashion. 3 10 -2 For the tree pictured, the call pathSum(13) would result in the following: pathSum(13) 10 12 6 Output: 13 23 13 Lesson 9 - Summer 2023 14
