Scribd
Upload
31 views6 pages

Binary Tree Implementation Lab Guide

Uploaded by

Sheikh Moosa Aijaz
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
31 views6 pages

Binary Tree Implementation Lab Guide

Uploaded by

Sheikh Moosa Aijaz
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd

DHA SUFFA UNIVERSITY

Department of Computer Science


CS-2001L
Data Structures & Algorithms Lab
Fall 2024
LAB 08

Objective
Learning about implementation of following concepts
• Binary Tree
• Binary Tree Traversal
o Pre-Order traversal
o In-Order traversal
o Post-Order traversal

Binary Trees
A binary tree T is defined as a finite set of elements, called nodes, such that
a) T is empty (called the null tree or empty tree), or
b) T contains a distinguished node R, called the root of T, and the remaining nodes of T
form an ordered pair of disjoint binary trees T1 and T2.
c) A tree whose elements have at most 2 children is called a binary tree. Since each
element in a binary tree can have only 2 children, we typically name them the left and
right child.

Example

Binary Tree Representation in Java:


A tree is represented by a reference to the topmost node in tree. If the tree is empty, then
value of root is null.
A Tree node contains following parts.
1. Data
2. Reference to left child
3. Reference to right child

In Java, we can represent a tree node using class Node. Below is an example of a tree node with
an integer data.

Creating Binary Tree


Traversing Binary Tree
Unlike linear data structures (Array, Linked List, Queues, Stacks, etc) which have only one logical
way to traverse them, trees can be traversed in different ways. Following are the generally used
ways for traversing trees.

Depth First Traversals:


(a) Preorder (Root, Left, Right) : 1 2 4 5 3
(b) Inorder (Left, Root, Right) : 4 2 5 1 3
(c) Postorder (Left, Right, Root) : 4 5 2 3 1

(a) Preorder
Algorithm Preorder(tree)
1. Visit the root.
2. Traverse the left subtree, i.e., call Preorder(left-subtree)
3. Traverse the right subtree, i.e., call Preorder(right-subtree)
Figure 1:This method is member of the [Link] class

(b) Inorder
Algorithm Inorder(tree)
1. Traverse the left subtree, i.e., call Inorder(left-subtree)
2. Visit the root.
3. Traverse the right subtree, i.e., call Inorder(right-subtree)Postorder

Figure 2: This method is member of the [Link] class


(c) Postorder
Algorithm Postorder(tree)
1. Traverse the left subtree, i.e., call Postorder(left-subtree)
2. Traverse the right subtree, i.e., call Postorder(right-subtree)
3. Visit the root.

Figure 3: This method is member of the [Link] class


TASKS
Perform the following tasks for binary tree, create separate function for each task.
1. Calculate level of the binary tree.
2. Check whether a given tree is complete tree, full tree or both.
3. Check the children sum property in binary tree, i.e. for every node data values must be
equal to the sum of data values of left and right child.

Submission Guidelines
• Write your codes in different notepad (.java) files with question number e.g. [Link]
• Place all files in a folder named your roll number e.g. cs162XXX.
• Compress all files into one (.zip) file named same as your roll number.
• Upload it on LMS
• -100 policies for plagiarism

Common questions

Powered by AI

A binary tree is distinguished by each node having at most two children, commonly referred to as the left and right child. This structure allows for specific traversal methods, such as Pre-order, In-order, and Post-order, which are unique due to the fixed positions of left and right children, enabling systematic ways to visit nodes .

Specific file naming and submission procedures, like naming files after questions or using a certain directory structure before submission, streamline organization, facilitate grading, and reduce errors during evaluation processes, ensuring uniformity .

To determine the level of a binary tree, a level-order traversal can be used, incrementing levels using a queue for holding nodes. Knowing the level aids in understanding the tree's height, which is essential for balancing and performance tuning in operations like search, insert, and delete .

A binary tree is complete if all levels, except possibly the last, are fully filled, and all nodes are as far left as possible. Completeness is crucial as it ensures efficient data storage and retrieval, particularly in binary heap implementations where such structure enhances priority queue performance .

Pre-order traversal involves visiting the root node first, followed by the left subtree and then the right subtree. This is significant in scenarios where the root needs processing before its children, such as copying a tree or used in prefix expressions .

The children sum property entails that a parent node's value equals the sum of its left and right children, applied in various contexts like specific arithmetic operation trees ensuring the integrity of functional outputs. It helps in certain types of expressions evaluations and verifying structural data integrity .

Non-compliance with submission guidelines, such as organizing and naming conventions, can lead to penalties like zero scores due to plagiarism checks or procedural non-adherence, impacting student grades and learning outcomes negatively .

In Java, a binary tree is represented by a Node class, which captures the conceptual structure of nodes having data and pointers to left and right children. This mirrors the theoretical definition, as each node contains data and two links analogous to children .

In-order traversal is advantageous for BSTs because it returns nodes in non-decreasing order, crucial for operations that require sorted data output. However, its limitation is inefficiency in balanced trees where obtainment of sorted data might not be uniformly distributed, potentially requiring full traversal .

Post-order traversal involves traversing the left subtree, the right subtree, and then visiting the root node. This method is particularly useful in scenarios like tree deletion, where child nodes must be processed before the parent node or evaluating a postfix expression .

You might also like