CareerCup4.4.cpp

CareerCup4.4.cpp

/*
  Chapter 4

  4.4 Given a binary tree, design an algorithm which creates a linked
  list of all the nodes at each depth. (e.g., if you have a tree with
  depth D, you'll have D linked lists.)

 */

#include <iostream>
#include <list>

using namespace std;

// Define tree_node struct
typedef struct tree_node {
    int value;
    struct tree_node* left;
    struct tree_node* right;
    tree_node(int value);
} tree_node;
// Constructor
tree_node::tree_node(int value) {
    this->value = value;
    left = NULL;
    right = NULL;
}

// return list<list<tree_node>>
list<list<tree_node>> depthList(tree_node root)
{
    // Initialization
    list<list<tree_node>> d_lists;
    list<tree_node> l;
    l.push_back(root);
    d_lists.push_back(l);
    // BFS style push back to newlist
    // then append newlist to d_lists
    for (list<list<tree_node>>::iterator i = d_lists.begin(); i != d_lists.end(); ++i)
    {
        list<tree_node> newlist;
        for (list<tree_node>::iterator j = i->begin(); j != i->end(); ++j)
        {
            if (j->left)
                newlist.push_back(*j->left);
            if (j->right)
                newlist.push_back(*j->right);
        }
        if (!newlist.empty())   // possible to have no element in newlist
            d_lists.push_back(newlist);
    }
    return d_lists;
}

/*Utility function*/
void printDL(list<list<tree_node>> DL, int depth)
{
    // Check range
    if (depth < 0 || depth > DL.size() - 1) {
        cout << "Error: The depth you entered is out of range!" << endl;
        return;
    }
    // Modify iterator to desire location
    list<list<tree_node>>::iterator i;
    i = DL.begin();
    for (int j = 0; j < depth; ++j) { ++i; }
    // Output all the node at this depth
    cout << "All the tree nodes in depth " << depth << " is: ";
    for (list<tree_node>::iterator k = i->begin(); k != i->end(); ++k)
    {
        cout << k->value << " ";
    }
    cout << endl;
}

// Main Function to test
int main()
{
    // Initialize a binary tree
    /*    3
         / \
        1   10
       /   /  \
      8   6    7   */
    tree_node root(3);
    tree_node l(1);
    tree_node ll(8);
    tree_node r(10);
    tree_node rl(6);
    tree_node rr(7);
    root.left = &l;
    root.right = &r;
    root.left->left = &ll;
    root.right->left = &rl; root.right->right = &rr;
    // Test
    list<list<tree_node>> DL;
    DL = depthList(root);
    cout << "Depth of this binary tree is: " << DL.size() - 1 << endl;
    printDL(DL, 0);
    printDL(DL, 1);
    printDL(DL, 2);
    printDL(DL, 3);
    return 0;
}

1. Good job! I think you can write the constructor inside the struct definition. But it's up to you.