Binary Tree Concepts Quiz

Choose a study mode

Play Quiz
Study Flashcards
Spaced Repetition
Chat to Lesson

Podcast

Play an AI-generated podcast conversation about this lesson

Questions and Answers

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.

postorder

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.

<p>binary</p> Signup and view all the answers

The sibling of the first child becomes the right child of the first child in the ______ tree.

<p>binary</p> Signup and view all the answers

A tree with outdegree of every node less than or equal to 2 is called a ______ tree.

<p>binary</p> Signup and view all the answers

The unique node in a binary tree is called the ______.

<p>root</p> Signup and view all the answers

The node to the left of the root is referred to as the ______ child.

<p>left</p> Signup and view all the answers

Nodes with the same parent are known as ______.

<p>siblings</p> Signup and view all the answers

A node with no children is classified as a ______.

<p>leaf</p> 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.

<p>descendant</p> Signup and view all the answers

The maximum number of nodes at any level N in a binary tree is given by 2______.

<p>N</p> Signup and view all the answers

The nodes which have no children are referred to as ______ nodes.

<p>external</p> Signup and view all the answers

The first node in the ______ traversal is the root of the binary tree.

<p>preorder</p> Signup and view all the answers

To find the nodes in the left subtree, use the ______ traversal.

<p>inorder</p> Signup and view all the answers

In inorder traversal, all nodes that are ______ to the root node are part of the left subtree.

<p>left</p> 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.

<p>postorder</p> Signup and view all the answers

We can determine the unique binary tree by repeatedly reading nodes from the ______ traversal.

<p>preorder</p> Signup and view all the answers

All nodes that are ______ of the root node in the inorder traversal are part of the right subtree.

<p>right</p> Signup and view all the answers

The unique binary tree can be constructed using both inorder and ______ traversals.

<p>preorder</p> 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.

<p>operator</p> Signup and view all the answers

A complete binary tree has the maximum number of possible ______ at all levels except possibly the last.

<p>nodes</p> Signup and view all the answers

In a full binary tree, every non-leaf node has ______ children.

<p>two</p> 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.

<p>preorder</p> Signup and view all the answers

Postorder traversal visits the root of the tree after traversing the left and right ______.

<p>subtrees</p> 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.

<p>inorder</p> 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.

<p>distinction</p> Signup and view all the answers

The depth of the complete binary tree having n nodes is given by the formula ______.

<p>log2 n + 1</p> Signup and view all the answers

Flashcards

Binary Tree

A tree where every node has a maximum of two children (0, 1, or 2).

Root Node

The unique starting node of a binary tree.

Left Child Node

The node directly below another node on the left side.

Right Child Node

The node directly below another node on the right side.

Signup and view all the flashcards

Parent Node

A node that has at least one child.

Signup and view all the flashcards

Sibling Nodes

Two nodes that share the same parent node.

Signup and view all the flashcards

Leaf Node

A node with NO children.

Signup and view all the flashcards

Level of a Node

The distance of a node from the root node. The root node's level is 0.

Signup and view all the flashcards

Depth or Height of a Tree

The maximum number of nodes along the longest path from root to a leaf node.

Signup and view all the flashcards

External Node (Terminal)

A node with NO children.

Signup and view all the flashcards

Internal Node (Non-Terminal)

A node that has at least one child.

Signup and view all the flashcards

Preorder Traversal

A traversal technique that visits the root node first, then the left subtree, and finally the right subtree.

Signup and view all the flashcards

Postorder Traversal

A traversal technique that visits the left subtree first, then the right subtree, and finally the root node.

Signup and view all the flashcards

Inorder Traversal

A traversal technique that visits the left subtree first, then the root node, and finally the right subtree.

Signup and view all the flashcards

Reconstructing a Binary Tree (Preorder, Inorder)

A technique to uniquely reconstruct a binary tree given its preorder and inorder traversals.

Signup and view all the flashcards

Reconstructing a Binary Tree (Postorder, Inorder)

A technique to uniquely reconstruct a binary tree given its postorder and inorder traversals.

Signup and view all the flashcards

Traversal Sequence

The sequence of nodes visited during a traversal.

Signup and view all the flashcards

Unique Binary Tree Construction

Creating a unique binary tree from a given Inorder and Postorder traversal of the tree. You use the information about where nodes appear in these traversals to reconstruct the entire tree structure.

Signup and view all the flashcards

General Tree to Binary Tree Conversion

Converting a general tree (where each node can have multiple children) into a binary tree, preserving the relationships between nodes.

Signup and view all the flashcards

Root Node of Binary Tree

The unique starting node of a binary tree, represented visually as the top node. It's the ancestor of all other nodes.

Signup and view all the flashcards

Binary Expression Tree

A binary expression tree is a tree-like structure used to represent arithmetic expressions. It's organized with operators at the nodes and operands at the leaves. This tree structure helps visually represent the order of operations.

Signup and view all the flashcards

Complete Binary Tree

In a complete binary tree, all levels except potentially the last one are completely filled with nodes. This means every level has the maximum number of nodes it can hold.

Signup and view all the flashcards

Full Binary Tree

A full binary tree has all its leaves at the same level, and every non-leaf node has two children. It means every node has either two children or none; no single child is allowed.

Signup and view all the flashcards

General Tree

A general tree is a hierarchical data structure with the possibility of having any number of children for each node. It's more flexible than a binary tree.

Signup and view all the flashcards

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.

Quiz Team

Related Documents

More Like This

Binary Search Tree Basics
5 questions

Binary Search Tree Basics

LuminousTanzanite5189 avatar
LuminousTanzanite5189
Binary Tree Traversals Chapter 5
36 questions
CS201 Data Structures Lecture 11
32 questions
Use Quizgecko on...
Browser
Browser