Podcast
Questions and Answers
The left child is obtained by selecting the last node in the ______ traversal of the left subtree.
The left child is obtained by selecting the last node in the ______ traversal of the left subtree.
postorder
The root of the binary tree is the last node in the ______ traversal.
The root of the binary tree is the last node in the ______ traversal.
postorder
All nodes that are left to the root node in inorder traversal are the nodes of the ______ subtree.
All nodes that are left to the root node in inorder traversal are the nodes of the ______ subtree.
left
The first child of the root node in the tree is the left child of the root node in the ______ tree.
The first child of the root node in the tree is the left child of the root node in the ______ tree.
Signup and view all the answers
The sibling of the first child becomes the right child of the first child in the ______ tree.
The sibling of the first child becomes the right child of the first child in the ______ tree.
Signup and view all the answers
A tree with outdegree of every node less than or equal to 2 is called a ______ tree.
A tree with outdegree of every node less than or equal to 2 is called a ______ tree.
Signup and view all the answers
The unique node in a binary tree is called the ______.
The unique node in a binary tree is called the ______.
Signup and view all the answers
The node to the left of the root is referred to as the ______ child.
The node to the left of the root is referred to as the ______ child.
Signup and view all the answers
Nodes with the same parent are known as ______.
Nodes with the same parent are known as ______.
Signup and view all the answers
A node with no children is classified as a ______.
A node with no children is classified as a ______.
Signup and view all the answers
A node is a ______ of another if it is a child or the child of some descendant of that node.
A node is a ______ of another if it is a child or the child of some descendant of that node.
Signup and view all the answers
The maximum number of nodes at any level N in a binary tree is given by 2______.
The maximum number of nodes at any level N in a binary tree is given by 2______.
Signup and view all the answers
The nodes which have no children are referred to as ______ nodes.
The nodes which have no children are referred to as ______ nodes.
Signup and view all the answers
The first node in the ______ traversal is the root of the binary tree.
The first node in the ______ traversal is the root of the binary tree.
Signup and view all the answers
To find the nodes in the left subtree, use the ______ traversal.
To find the nodes in the left subtree, use the ______ traversal.
Signup and view all the answers
In inorder traversal, all nodes that are ______ to the root node are part of the left subtree.
In inorder traversal, all nodes that are ______ to the root node are part of the left subtree.
Signup and view all the answers
The right child of the root is obtained by selecting the last node in the ______ traversal of the right subtree.
The right child of the root is obtained by selecting the last node in the ______ traversal of the right subtree.
Signup and view all the answers
We can determine the unique binary tree by repeatedly reading nodes from the ______ traversal.
We can determine the unique binary tree by repeatedly reading nodes from the ______ traversal.
Signup and view all the answers
All nodes that are ______ of the root node in the inorder traversal are part of the right subtree.
All nodes that are ______ of the root node in the inorder traversal are part of the right subtree.
Signup and view all the answers
The unique binary tree can be constructed using both inorder and ______ traversals.
The unique binary tree can be constructed using both inorder and ______ traversals.
Signup and view all the answers
The expression tree is a binary tree whose root contains the ______ and whose left subtree contains the left expression.
The expression tree is a binary tree whose root contains the ______ and whose left subtree contains the left expression.
Signup and view all the answers
A complete binary tree has the maximum number of possible ______ at all levels except possibly the last.
A complete binary tree has the maximum number of possible ______ at all levels except possibly the last.
Signup and view all the answers
In a full binary tree, every non-leaf node has ______ children.
In a full binary tree, every non-leaf node has ______ children.
Signup and view all the answers
The binary tree traversal method that visits the root, then the left subtree, followed by the right subtree is called ______ traversal.
The binary tree traversal method that visits the root, then the left subtree, followed by the right subtree is called ______ traversal.
Signup and view all the answers
Postorder traversal visits the root of the tree after traversing the left and right ______.
Postorder traversal visits the root of the tree after traversing the left and right ______.
Signup and view all the answers
The method of tree traversal that processes the left subtree, root, and then the right subtree is known as ______ traversal.
The method of tree traversal that processes the left subtree, root, and then the right subtree is known as ______ traversal.
Signup and view all the answers
If some node in a general tree has a child, there is no such ______ as a left child or a right child.
If some node in a general tree has a child, there is no such ______ as a left child or a right child.
Signup and view all the answers
The depth of the complete binary tree having n nodes is given by the formula ______.
The depth of the complete binary tree having n nodes is given by the formula ______.
Signup and view all the answers
Study Notes
Binary Trees
- A binary tree is a directed tree where each node has an outdegree less than or equal to 2.
- An empty tree is also considered a binary tree.
- Binary tree nodes are characterized by their relationships to the root.
Basic Terminology
- Root: The unique node at the top of the tree.
- Left Child: The node directly to the left of the root.
- Right Child: The node directly to the right of the root.
- Parent: A node with a left or right child, or both.
- Siblings: Nodes sharing the same parent.
- Leaf: A node with no children.
- Descendant: A node that is a child or descendant of another node.
- Left Subtree: The subtree whose root is the left child of a node.
- Right Subtree: The subtree whose root node is the right child of some node.
Level of a Node
- The level of a node is its distance from the root.
- The root's level is 0.
- Each level is one more than its parent (upward).
- Maximum number of nodes at level N is 2N (exponentially increases)
Depth or Height of a Tree
- The depth or height is the maximum number of nodes in a branch of the tree
- The depth of a root is 1
- Maximum number of nodes in a binary tree with depth d is 2d-1 (starting from 1, then 2, 4, etc.)
External and Internal Nodes
- External Nodes: Nodes with no children (terminal nodes)
- Internal Nodes: Nodes with one or more than one children (non-terminal nodes)
Binary Expression Trees
- Algebraic expressions can be represented conveniently by binary expression trees.
- Tree is decomposed into left operand, operator and right operand (or expressions)
- The evaluation of the tree depends on the operator precedence.
Complete Binary Tree
- A complete binary tree has all levels full, except possibly the last, containing the maximum number of nodes possible for the given level.
- The depth of a complete binary tree with n nodes is log2n + 1
Full Binary Tree
- A full binary tree is a binary tree where all the leaves are at the same level.
- Each non-leaf node has two children
General vs. Binary Tree
- A general tree can have zero nodes or an empty node.
- In a binary tree, an empty tree may be possible.
- If a node has a child, different distinctions are made (left/right children)
- Equivalent general trees can be distinct in a binary representation.
Tree Traversal
- Preorder Traversal: Visit the root, traverse the left subtree in preorder, traverse the right subtree in preorder
- Postorder Traversal: Traverse the left subtree in postorder, traverse the right subtree in postorder, visit the root
- Inorder Traversal: Traverse the left subtree in inorder, visit the root, traverse the right subtree in inorder
Drawing a Unique Binary Tree
- The root is the first node in the preorder traversal.
- Use the inorder traversal to find nodes for the left and right subtrees
- Repeat with each node until all are evaluated.
Studying That Suits You
Use AI to generate personalized quizzes and flashcards to suit your learning preferences.
Related Documents
Description
Test your knowledge of binary tree concepts with this quiz. Covering essential terminology and properties, this quiz will help reinforce your understanding of binary trees and their structure. Perfect for students and enthusiasts of computer science.
