Tag: §

Preamble
None standard tree traversals. Determine the height of a tree, and height order tree traversal. Often used as interview questions.

Determine height of a tree
Iterate to the bottom of the tree and on returning return the max height of each branch, add one for this current level.

Code:
[js]
int height(Node* node_)
{
if (node_ == nullptr)
{
return 0;
}

int left = height(node_->_left);
int right = height(node_->_right);

return max(left, right) + 1;
}
[/js]

Height order traversal
Iterate over all nodes by using a queue to push each level into the queue as it occurs.

Code:
[js]
queue d;

void heightWiseTransversal(Node* node_)
{
if (node_ == nullptr)
{
return;
}

cout << node_->_data << endl; d.push(node_->_left);
d.push(node_->_right);

Node* frontNode1 = d.front();
d.pop();
heightWiseTransversal(frontNode1);

Node* frontNode2 = d.front();
d.pop();
heightWiseTransversal(frontNode2);
}
[/js]

Full code
Just in case you want to run it.

[js]
#include
#include
#include
using namespace std;

class Node
{
public:
Node(string data_, Node* left_, Node* right_) : _data(data_), _left(left_), _right(right_) {}
string _data;
Node* _left;
Node* _right;
};

queue d;

void heightWiseTransversal(Node* node_)
{
if (node_ == nullptr)
{
return;
}

cout << node_->_data << endl; d.push(node_->_left);
d.push(node_->_right);

Node* frontNode1 = d.front();
d.pop();
heightWiseTransversal(frontNode1);

Node* frontNode2 = d.front();
d.pop();
heightWiseTransversal(frontNode2);
}

int height(Node* node_)
{
if (node_ == nullptr)
{
return 0;
}

int left = height(node_->_left);
int right = height(node_->_right);

return max(left, right) + 1;
}

int main()
{
//Note I keep lifetime management separate from functionality!

unique_ptr G = make_unique(“G4”, nullptr, nullptr);
unique_ptr F = make_unique(“F3”, nullptr, nullptr);
unique_ptr E = make_unique(“E3”, nullptr, nullptr);
unique_ptr D = make_unique(“D3”, G.get(), nullptr);
unique_ptr C = make_unique(“C2”, E.get(), F.get());
unique_ptr B = make_unique(“B2”, D.get(), nullptr);
unique_ptr A = make_unique(“A1”, B.get(), C.get());

cout << "Height wise traversal" << endl; heightWiseTransversal(A.get()); cout << endl; cout << "height = " << height(A.get()) << endl; return 0; } [/js] Output
Height wise traversal
A1
B2
C2
D3
E3
F3
G4

Height = 4