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.
	BinaryTree (const BinaryTree &)=delete
BinaryTree &	operator= (const BinaryTree &)=delete

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.

Definition at line 52 of file reverse_binary_tree.cpp.

Constructor & Destructor Documentation

BinaryTree() [1/2]

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

inline

Creates a BinaryTree with a root pointing to NULL.

Definition at line 101 of file reverse_binary_tree.cpp.

{ 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.

Definition at line 105 of file reverse_binary_tree.cpp.

{ root = new Node(data); }

~BinaryTree()

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

inline

Definition at line 107 of file reverse_binary_tree.cpp.

                  {
        std::vector<Node*> nodes;
        nodes.emplace_back(root);
        while (!nodes.empty()) {
            const auto cur_node = nodes.back();
            nodes.pop_back();
            if (cur_node) {
                nodes.emplace_back(cur_node->left);
                nodes.emplace_back(cur_node->right);
                delete cur_node;
            }
        }
    }

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.

Definition at line 124 of file reverse_binary_tree.cpp.

{ root = insert(data, root); }

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

Definition at line 139 of file reverse_binary_tree.cpp.

                                         {
        std::vector<int64_t> data;  
        if (root == nullptr) {
            return data;  
        }
        std::queue<Node*> nodes;  
        nodes.push(root);         
        while (!nodes.empty()) {
            Node* temp = nodes.front();  
            data.push_back(temp->data);  
            nodes.pop();                 
            if (temp->left != nullptr) {
                nodes.push(temp->left);  
            }
            if (temp->right != nullptr) {
                nodes.push(temp->right);  
            }
        }  
        return data;
    }

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

Definition at line 65 of file reverse_binary_tree.cpp.

                                            {
        if (pivot == nullptr) {
            return new Node(data);  
        }
        if (data <= pivot->data) {
            pivot->left =
                insert(data, pivot->left);  
        } else {
            pivot->right =
                insert(data, pivot->right);  
        }
        return pivot;
    }

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

Definition at line 164 of file reverse_binary_tree.cpp.

                 {
        for (int i : get_level_order()) {
            std::cout << i << " ";  
        }
        std::cout << "\n";  
    }

reverse()

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

inline

Reverses the Binary Tree

Definition at line 128 of file reverse_binary_tree.cpp.

{ root = reverseBinaryTree(root); }

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

Definition at line 84 of file reverse_binary_tree.cpp.

                                         {
        if (pivot == nullptr) {
            return pivot;  
        }
        Node* temp = pivot->left;  
        pivot->left = reverseBinaryTree(pivot->right);  
        pivot->right = reverseBinaryTree(temp);         
        return pivot;
    }

Member Data Documentation

root

Node* operations_on_datastructures::reverse_binary_tree::BinaryTree::root

private

Pointer to root node of Binary Tree.

Definition at line 54 of file reverse_binary_tree.cpp.

---

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

• operations_on_datastructures/reverse_binary_tree.cpp