How to Pretty Print a Binary Tree | LeetCode

How to Pretty Print a Binary Tree | LeetCode
Have you ever thought of pretty-printing a binary tree?

        ______30______
       /              \
    __20__          __40__
   /      \        /      \
  10      25      35      50
 /  \       \            /   
 5  15      28          41

For a level, each node is spaced equally with neighboring nodes. This allows a Math equation to be derived easily to calculate the exact location a node will appear in a level.

Last time, when we see an “empty” node, we do not push anything onto the queue. However, this time we need to push two “empty” nodes when we see an “empty” node, since we need to print out the “empty” node as spaces in order to produce a pretty output. Besides, it eases the programming a lot since we do not need to keep track of the number of empty nodes that appear before a valid node.

// Print the arm branches (eg, /    \ ) on a line

void printBranches(int branchLen, int nodeSpaceLen, int startLen, int nodesInThisLevel, const deque<BinaryTree*>& nodesQueue, ostream& out) {

  deque<BinaryTree*>::const_iterator iter = nodesQueue.begin();

  for (int i = 0; i < nodesInThisLevel / 2; i++) {  

    out << ((i == 0) ? setw(startLen-1) : setw(nodeSpaceLen-2)) << "" << ((*iter++) ? "/" : " ");

    out << setw(2*branchLen+2) << "" << ((*iter++) ? "\\" : " ");

  }

  out << endl;

}

// Print the branches and node (eg, ___10___ )

void printNodes(int branchLen, int nodeSpaceLen, int startLen, int nodesInThisLevel, const deque<BinaryTree*>& nodesQueue, ostream& out) {

  deque<BinaryTree*>::const_iterator iter = nodesQueue.begin();

  for (int i = 0; i < nodesInThisLevel; i++, iter++) {

    out << ((i == 0) ? setw(startLen) : setw(nodeSpaceLen)) << "" << ((*iter && (*iter)->left) ? setfill('_') : setfill(' '));

    out << setw(branchLen+2) << ((*iter) ? intToString((*iter)->data) : "");

    out << ((*iter && (*iter)->right) ? setfill('_') : setfill(' ')) << setw(branchLen) << "" << setfill(' ');

  }

  out << endl;

}

// Print the leaves only (just for the bottom row)

void printLeaves(int indentSpace, int level, int nodesInThisLevel, const deque<BinaryTree*>& nodesQueue, ostream& out) {

  deque<BinaryTree*>::const_iterator iter = nodesQueue.begin();

  for (int i = 0; i < nodesInThisLevel; i++, iter++) {

    out << ((i == 0) ? setw(indentSpace+2) : setw(2*level+2)) << ((*iter) ? intToString((*iter)->data) : "");

  }

  out << endl;

}

// Pretty formatting of a binary tree to the output stream

// @ param

// level  Control how wide you want the tree to sparse (eg, level 1 has the minimum space between nodes, while level 2 has a larger space between nodes)

// indentSpace  Change this to add some indent space to the left (eg, indentSpace of 0 means the lowest level of the left node will stick to the left margin)

void printPretty(BinaryTree *root, int level, int indentSpace, ostream& out) {

  int h = maxHeight(root);

  int nodesInThisLevel = 1;

  int branchLen = 2*((int)pow(2.0,h)-1) - (3-level)*(int)pow(2.0,h-1);  // eq of the length of branch for each node of each level

  int nodeSpaceLen = 2 + (level+1)*(int)pow(2.0,h);  // distance between left neighbor node's right arm and right neighbor node's left arm

  int startLen = branchLen + (3-level) + indentSpace;  // starting space to the first node to print of each level (for the left most node of each level only)

    

  deque<BinaryTree*> nodesQueue;

  nodesQueue.push_back(root);

  for (int r = 1; r < h; r++) {

    printBranches(branchLen, nodeSpaceLen, startLen, nodesInThisLevel, nodesQueue, out);

    branchLen = branchLen/2 - 1;

    nodeSpaceLen = nodeSpaceLen/2 + 1;

    startLen = branchLen + (3-level) + indentSpace;

    printNodes(branchLen, nodeSpaceLen, startLen, nodesInThisLevel, nodesQueue, out);

    for (int i = 0; i < nodesInThisLevel; i++) {

      BinaryTree *currNode = nodesQueue.front();

      nodesQueue.pop_front();

      if (currNode) {

       nodesQueue.push_back(currNode->left);

       nodesQueue.push_back(currNode->right);

      } else {

        nodesQueue.push_back(NULL);

        nodesQueue.push_back(NULL);

      }

    }

    nodesInThisLevel *= 2;

  }

  printBranches(branchLen, nodeSpaceLen, startLen, nodesInThisLevel, nodesQueue, out);

  printLeaves(indentSpace, level, nodesInThisLevel, nodesQueue, out);

}

http://blog.csdn.net/nicaishibiantai/article/details/45006709
http://www.fgdsb.com/2015/01/25/pretty-print-bst/

int max_height(TreeNode* node) {

    if(!node) return 0;

    return 1 + max(max_height(node->left), max_height(node->right));

}



void pretty_print_bst(TreeNode* root, int space_size = 3) {    

    deque<TreeNode*> q = { root };    

    

    int height = max_height(root);

    int cur_level_nodes = 1, next_level_nodes = 0, level = 1;

    int padding = space_size * (pow(2, height - level) - 1);

    cout << setw(padding / 2) << "";



    while (level <= height) {

        cout << setw(space_size);

        if (q.front()) {

            cout << q.front()->val;

            q.push_back(q.front()->left);

            q.push_back(q.front()->right);

        } else {

            cout << " ";

            q.push_back(nullptr);

            q.push_back(nullptr);

        }

        next_level_nodes += 2;

        cout << setw(padding) << "";

        q.pop_front();



        // go to next level

        if (--cur_level_nodes == 0) {

            cur_level_nodes = next_level_nodes;

            next_level_nodes = 0;

            ++level;

            padding = space_size * (pow(2, height - level) - 1);

            cout << endl << setw(padding / 2) << "";

        }

    }

}

Read full article from How to Pretty Print a Binary Tree | LeetCode