Understanding Binary Trees: Definitions, Properties, and Terminology
Explore the world of binary trees, including definitions, properties like depth and height, and essential terminology like root nodes, children, and leaves. Learn how to represent binary trees and solve common tree traversal problems such as DFS and BFS.
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 Trees Definitions and terminology Binary trees Definitions and property Binary trees case studies: Depth first values problem Depth First Search (DFS) Breadth first values problem Breadth First Search (BFS) Tree includes problem
Tree Definition A finite set of one or more nodes One node is root Root node in tree below is A And each one of the remaining nodes has Only one parent A C B D E F G H
A Terminology C B In this tree A is the root node B is the parent of D and E C is the sibling of B D and E are the children of B D, E, F, G, and H are leaves (or external nodes) A, B, and C are internal nodes D E F G H Subtree rooted at C The subtree rooted at C includes the C, F, G, and H nodes
A Binary Tree C B F G D E Properties Every node has at most two children Denoted by left and right children Subtree rooted at left child => left subtree Subtree rooted at right child => right subtree In a proper binary tree Each node has either zero or two children Otherwise, it is called improper
Depth of a node The depth of a tree node Is the number of ancestors of the node Depth of root node = 0 In tree below, depth(D) = 2, since it has 2 ancestors, A and B Nodes of same depth form a level Depth = 0 Level 0 A Level 1 Depth = 1 C B Level 2 F G Depth = 2 D E
Height of a node/tree Height of a node If it is external, then height = 0 Otherwise, height = 1 + height of max height of children Height of a tree = height of root It is also equal to depth of deepest node Height of this tree = 2 A Height of C = 1 C B F G D E Height of F = 0
Binary tree representation BTNode element A right left B C D E F BTNode<T> class T element BTNode<T> left BTNode<T> right
Binary tree case study 1: depth first values Depth first traversal of binary tree Storing elements in an array list A B C D E F This results in following list A, B, D, E, C, 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 D E F This results in following list A, B, C, D, E, F Solution Iterative solution: Queue-based
Binary tree case study 3: tree includes Objective Find a target node value in the tree A B C This results in True if value is found in tree False, otherwise D E F Solution Recursive traversal-based solution
