operations_on_datastructures::reverse_binary_tree::BinaryTree Class Reference

A Binary Tree class that implements a Binary Search Tree (BST) by default. More...

Collaboration diagram for operations_on_datastructures::reverse_binary_tree::BinaryTree:

Public Member Functions
	BinaryTree ()
	Creates a BinaryTree with a root pointing to NULL.
	BinaryTree (int64_t data)
	Creates a BinaryTree with a root with an initial value.
void	add (int64_t data)
	Adds a new Node to the Binary Tree.
void	reverse ()
std::vector< int64_t >	get_level_order ()
	Level order traversal of a tree consists of visiting its elements, top to bottom, left to right. This function performs level order traversal and returns the node datas as a vector.
void	print ()
	Prints all of the elements in the tree to stdout level-by-level, using the get_level_order() function.

Private Member Functions
Node *	insert (int64_t data, Node *pivot)
	inserts a node in the Binary Tree, with the behaviouur of a Binary Search Tree.
Node *	reverseBinaryTree (Node *pivot)
	Reverses a Binary Tree recursively by swapping the left and right subtrees and their children.

Private Attributes
Node *	root
	Pointer to root node of Binary Tree.

Detailed Description

A Binary Tree class that implements a Binary Search Tree (BST) by default.

Constructor & Destructor Documentation

BinaryTree() [1/2]

operations_on_datastructures::reverse_binary_tree::BinaryTree::BinaryTree ( )

inline

Creates a BinaryTree with a root pointing to NULL.

{ root = nullptr; }

BinaryTree() [2/2]

operations_on_datastructures::reverse_binary_tree::BinaryTree::BinaryTree ( int64_t data )

inlineexplicit

Creates a BinaryTree with a root with an initial value.

{ root = new Node(data); }

Member Function Documentation

add()

void operations_on_datastructures::reverse_binary_tree::BinaryTree::add ( int64_t data )

inline

Adds a new Node to the Binary Tree.

{ root = insert(data, root); }

Here is the call graph for this function:

get_level_order()

std::vector< int64_t > operations_on_datastructures::reverse_binary_tree::BinaryTree::get_level_order ( )

inline

Level order traversal of a tree consists of visiting its elements, top to bottom, left to right. This function performs level order traversal and returns the node datas as a vector.

The function uses a queue to append and remove elements as they are visited, and then adds their children, if any. This ensures that the elements are visited layer-by-layer, starting from the root of the Tree.

Returns

vector<int64_t> of nodes of the tree.

< Result vector of int

< Return empty vector if root is Invalid

< Queue of the nodes in the tree

< Insert root into the queue

< Copy the first element

< Add the element to the data

< Remove element

< Insert left node

< Insert right node

Add nodes while Tree is not empty

                                         {
        std::vector<int64_t> data;  ///< Result vector of int
        if (root == nullptr) {
            return data;  ///< Return empty vector if root is Invalid
        }
        std::queue<Node*> nodes;  ///< Queue of the nodes in the tree
        nodes.push(root);         ///< Insert root into the queue
        while (!nodes.empty()) {
            Node* temp = nodes.front();  ///< Copy the first element
            data.push_back(temp->data);  ///< Add the element to the data
            nodes.pop();                 ///< Remove element
            if (temp->left != nullptr) {
                nodes.push(temp->left);  ///< Insert left node
            }
            if (temp->right != nullptr) {
                nodes.push(temp->right);  ///< Insert right node
            }
        }  /// Add nodes while Tree is not empty
        return data;
    }

Here is the call graph for this function:

insert()

Node * operations_on_datastructures::reverse_binary_tree::BinaryTree::insert ( int64_t data, Node * pivot )

inlineprivate

inserts a node in the Binary Tree, with the behaviouur of a Binary Search Tree.

Nodes with smaller values are inserted in the left subtree, and Nodes with larger values are inserted into the right subtree recursively. Time Complexity: O(log(n))

Parameters

data	The data/value of the Node to be inserted
pivot	A pointer to the root node of the (sub)tree

Returns

Node pointer to the root

< Create new node

< Insert Node to the left

< Insert node to the right

                                            {
        if (pivot == nullptr) {
            return new Node(data);  ///< Create new node
        }
        if (data <= pivot->data) {
            pivot->left =
                insert(data, pivot->left);  ///< Insert Node to the left
        } else {
            pivot->right =
                insert(data, pivot->right);  ///< Insert node to the right
        }
        return pivot;
    }

Here is the call graph for this function:

print()

void operations_on_datastructures::reverse_binary_tree::BinaryTree::print ( )

inline

Prints all of the elements in the tree to stdout level-by-level, using the get_level_order() function.

Returns

void

Print each element in the tree

Print newline

                 {
        for (int i : get_level_order()) {
            std::cout << i << " ";  /// Print each element in the tree
        }
        std::cout << "\n";  /// Print newline
    }

Here is the call graph for this function:

reverse()

void operations_on_datastructures::reverse_binary_tree::BinaryTree::reverse ( )

inline

Reverses the Binary Tree

{ root = reverseBinaryTree(root); }

Here is the call graph for this function:

reverseBinaryTree()

Node * operations_on_datastructures::reverse_binary_tree::BinaryTree::reverseBinaryTree ( Node * pivot )

inlineprivate

Reverses a Binary Tree recursively by swapping the left and right subtrees and their children.

Parameters

pivot

A reference to the root of the (sub)tree

Returns

Node pointer to root node

< Base case

< pointer to the left subtree

< Swap

< Swap

                                         {
        if (pivot == nullptr) {
            return pivot;  ///< Base case
        }
        Node* temp = pivot->left;  ///< pointer to the left subtree
        pivot->left = reverseBinaryTree(pivot->right);  ///< Swap
        pivot->right = reverseBinaryTree(temp);         ///< Swap
        return pivot;
    }

Here is the call graph for this function:

---

The documentation for this class was generated from the following file:

• operations_on_datastructures/reverse_binary_tree.cpp