A RetroSearch Logo

Home - News ( United States | United Kingdom | Italy | Germany ) - Football scores

Search Query:

Showing content from https://TheAlgorithms.github.io/C-Plus-Plus/d4/d32/inorder__successor__of__bst_8cpp_source.html below:

TheAlgorithms/C++: operations_on_datastructures/inorder_successor_of_bst.cpp Source File

Go to the documentation of this file. 51namespace

inorder_traversal_of_bst {

71 node

->left =

nullptr

;

72 node

->right =

nullptr

;

83 if

(root ==

nullptr

) {

101 if

(root ==

nullptr

) {

103

}

else if

(root->data ==

data

) {

105

}

else if

(

data

> root->data) {

122 if

(root ==

nullptr

) {

125 while

(root->left !=

nullptr

) {

137 if

(root ==

nullptr

) {

142

std::cout << root->data <<

" "

;

156 for

(int64_t values :

data

) {

157

root =

Insert

(root, values);

178 if

(current ==

nullptr

) {

183 if

(current->

right

!=

nullptr

) {

188 Node

*successor =

nullptr

;

189 Node

*ancestor = root;

191 while

(ancestor != current && ancestor !=

nullptr

) {

193 if

(current->

data

< ancestor->

data

) {

194

successor = ancestor;

195

ancestor = ancestor->

left

;

197

ancestor = ancestor->

right

;

211 if

(rootNode ==

nullptr

) {

232 template

<

typename

T>

235

std::cout <<

"[TESTS] : ---> "

<< msg << std::endl;

244 log

(

"Running Tests..."

);

250 log

(

"Test Cases over!"

);

251

std::cout << std::endl;

261

*expectedOutput =

nullptr

;

263 log

(

"~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~"

);

264 log

(

"This is test case 1 : "

);

265 log

(

"Description:"

);

266 log

(

" EDGE CASE : Printing inorder successor for last node in the " 267 "BST, Output will be nullptr."

);

271

std::vector<int64_t> node_data{

272

20, 3, 5, 6, 2, 23, 45, 78, 21};

278

std::cout <<

"Inorder sequence is : "

;

281

std::cout << std::endl;

284

*inorderSuccessor = operations_on_datastructures::

285

inorder_traversal_of_bst::getInorderSuccessor(

288 log

(

"Checking assert expression..."

);

289

assert(inorderSuccessor == expectedOutput);

290 log

(

"Assertion check passed!"

);

295 log

(

"[PASS] : TEST CASE 1 PASS!"

);

296 log

(

"~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~"

);

305 const int

expectedOutput = 21;

307 log

(

"~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~"

);

308 log

(

"This is test case 2 : "

);

312

std::vector<int64_t> node_data{

313

20, 3, 5, 6, 2, 23, 45, 78, 21};

319

std::cout <<

"Inorder sequence is : "

;

322

std::cout << std::endl;

325

*inorderSuccessor = operations_on_datastructures::

326

inorder_traversal_of_bst::getInorderSuccessor(

329 log

(

"Checking assert expression..."

);

330

assert(inorderSuccessor->

data

== expectedOutput);

331 log

(

"Assertion check passed!"

);

336 log

(

"[PASS] : TEST CASE 2 PASS!"

);

337 log

(

"~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~"

);

346 const int

expectedOutput = 110;

348 log

(

"~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~"

);

349 log

(

"This is test case 3 : "

);

353

std::vector<int64_t> node_data{

354

89, 67, 32, 56, 90, 123, 120,

355

110, 115, 6, 78, 7, 10};

361

std::cout <<

"Inorder sequence is : "

;

364

std::cout << std::endl;

367

*inorderSuccessor = operations_on_datastructures::

368

inorder_traversal_of_bst::getInorderSuccessor(

371 log

(

"Checking assert expression..."

);

372

assert(inorderSuccessor->

data

== expectedOutput);

373 log

(

"Assertion check passed!"

);

378 log

(

"[PASS] : TEST CASE 3 PASS!"

);

379 log

(

"~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~"

);

401

std::vector<int64_t> node_data{3, 4, 5,

404

int64_t targetElement = 4;

409

*inorderSuccessor = operations_on_datastructures::

410

inorder_traversal_of_bst::getInorderSuccessor(root, targetElement);

412

std::cout <<

"In-order sequence is : "

;

414

std::cout << std::endl;

416 if

(inorderSuccessor ==

nullptr

) {

417

std::cout <<

"Inorder successor for last node is NULL"

<< std::endl;

419

std::cout <<

"Target element is : "

<< targetElement << std::endl;

420

std::cout <<

"Inorder successor for target element is : " 421

<< inorderSuccessor->

data

<< std::endl;

class encapsulating the necessary test cases

void log(T msg)

A function to print given message on console.

void testCase_2()

A test case which contains main list of 100 elements and sublist of 20.

void testCase_1()

A test case contains edge case, printing inorder successor of last node.

void testCase_3()

A test case which contains main list of 50 elements and sublist of 20.

void runTests()

Executes test cases.

A Node structure representing a single node in BST.

Node * right

Pointer to right child.

Node * left

Pointer to Left child.

int64_t data

The key/value of the node.

Node * makeBST(Node *root, const std::vector< int64_t > &data)

This function is used in test cases to quickly create BST containing large data instead of hard codin...

Node * getInorderSuccessor(Node *root, int64_t data)

Inorder successor of a node is the next node in inorder traversal of the Binary Tree....

Node * Insert(Node *root, int64_t data)

Inserts the given data in BST while maintaining the properties of BST.

void printInorder(Node *root)

Prints the BST in inorder traversal using recursion.

Node * findMinNode(Node *root)

Finds and return the minimum node in BST.

void deallocate(Node *rootNode)

This function clears the memory allocated to entire tree recursively. Its just for clean up the memor...

Node * makeNode(int64_t data)

Allocates a new node in heap for given data and returns it's pointer.

Node * getNode(Node *root, int64_t data)

Searches the given data in BST and returns the pointer to the node containing that data.

static void test()

Self-test implementations.

int main()

Main function.

RetroSearch is an open source project built by @garambo | Open a GitHub Issue

Search and Browse the WWW like it's 1997 | Search results from DuckDuckGo

HTML: 3.2 | Encoding: UTF-8 | Version: 0.7.4