Exploring Binary Trees in CSE 123 Winter 2025
Delve into the world of binary trees in the CSE 123 course for Winter 2025. Learn about the structure, traversals, and terminologies associated with binary trees. Get ready for the final exam and programming assignments while enjoying the engaging lecture tunes and interactive 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
LEC 13: Binary Trees CSE 123 Winter 2025 BEFORE WE START Talk to your neighbors: LEC 13 What s your favorite tree? CSE 123 CSE 123 Instructors: Brett Wortzman Miya Natsuhara TAs: Binary Trees Arohan Neha Rushil Johnathan Nicholas Sean Hayden Srihari Benoit Isayiah Audrey Chris Andras Jessica Kavya Cynthia Shreya Kieran Rohan Eeshani Amy Packard Cora Dixon Nichole Questions during Class? Trien Lawrence Liza Helena Raise hand or send here Music: CSE 123 25wi Lecture Tunes sli.do #cse123
LEC 13: Binary Trees CSE 123 Winter 2025 Lecture Outline Announcements Binary Tree Review Traversals Practice!
LEC 13: Binary Trees CSE 123 Winter 2025 Announcements Resubmission Cycle 4 is due tonight at 11:59pm - C1, P1 eligible Programming Assignment 2 is out, due Wednesday (Feb 26) Final Exam: Tuesday, March 18 at 12:30pm 2:20pm
LEC 13: Binary Trees CSE 123 Winter 2025 Lecture Outline Announcements Binary Tree Review Traversals Practice!
LEC 13: Binary Trees CSE 123 Winter 2025 Binary Trees Last data structure of the quarter! - Very similar to LinkedLists data next front 1 2 3 null
LEC 13: Binary Trees CSE 123 Winter 2025 Binary Trees front Last data structure of the quarter! - Very similar to LinkedLists 1 data next 2 3 null
LEC 13: Binary Trees CSE 123 Winter 2025 Binary Trees overallRoot Last data structure of the quarter! - Very similar to LinkedLists 1 data right left Linked TreeNodes w/ 3 fields: - int data, TreeNode left, TreeNode right - Doubly complicated! null 2 null 3 null null
LEC 13: Binary Trees CSE 123 Winter 2025 Binary Trees overallRoot root Last data structure of the quarter! - Very similar to LinkedLists 1 data right left Linked TreeNodes w/ 3 fields: - int data, TreeNode left, TreeNode right - Doubly complicated! null 2 leaves Similar to trees? - Close enough! - Terminology: root / leaves 3 4 null null null Other terminology as well
LEC 13: Binary Trees CSE 123 Winter 2025 Tree Terminology overallRoot 1 data parent / child right left null 2 3 4 null null null
LEC 13: Binary Trees CSE 123 Winter 2025 Tree Terminology overallRoot 1 data right left null 2 siblings 3 4 null null null
LEC 13: Binary Trees CSE 123 Winter 2025 Linked Lists [Review] A linked list is either: data next null 4 another list Node w/ another linked list Empty list This is a recursive definition! A list is either empty or a node with another list!
LEC 13: Binary Trees CSE 123 Winter 2025 Binary Trees A Binary Tree is either: 1 null Tree Tree Empty tree Node w/ two subtrees This is a recursive definition! A tree is either empty or a node with two more trees!
LEC 13: Binary Trees CSE 123 Winter 2025 Binary Tree Programming Programs look very similar to Recursive LinkedList! Guaranteed base case: empty tree - Simplest possible input, should immediately know the return Guaranteed public / private pair - Need to know which subtree you re currently processing If modifying, we use x = change(x) - Don t stop early, return updated subtree (IntTreeNode) Let s trace through an example together
LEC 13: Binary Trees CSE 123 Winter 2025 Tracing Through Binary Tree Programming Pre-order traversal 1 method(one) 2 3 method(two) method(three) method(null) method(null) null null null method(null) method(null)
LEC 13: Binary Trees CSE 123 Winter 2025 Lecture Outline Announcements Binary Tree Review Traversals Practice!
LEC 13: Binary Trees CSE 123 Winter 2025 Binary Tree Traversals 3 different primary traversals - All concerned with when you process your current root 1 Pre-order traversal: - Process root, left subtree, right subtree In-order traversal: - Process left subtree, root, right subtree Post-order traversal: - Process left subtree, right subtree, root 2 3 null null null Sometimes different traversals yield different results
LEC 13: Binary Trees CSE 123 Winter 2025 Practice : Think Enter the order in which the nodes of this tree would be visited in a pre-order traversal. 6 sli.do #cse123 2 3 1 4 6 4
LEC 13: Binary Trees CSE 123 Winter 2025 Practice : Pair Enter the order in which the nodes of this tree would be visited in a pre-order traversal. 6 sli.do #cse123 2 3 1 4 6 4
LEC 13: Binary Trees CSE 123 Winter 2025 Practice : Pair Enter the order in which the nodes of this tree would be visited in an in-order traversal. 6 sli.do #cse123 2 3 1 4 6 4
LEC 13: Binary Trees CSE 123 Winter 2025 Practice : Pair Enter the order in which the nodes of this tree would be visited in a post-order traversal. 6 sli.do #cse123 2 3 1 4 6 4
LEC 13: Binary Trees CSE 123 Winter 2025 Lecture Outline Announcements Binary Tree Review Traversals Practice!
LEC 13: Binary Trees CSE 123 Winter 2025 Tracing through size public int size() { return size(overallRoot); } private int size(IntTreeNode currentRoot) { if (currentRoot == null) { return 0; } else { return 1 + size(currentRoot.left) + size(currentRoot.right); } } 6 2 3 1 4 6 4
