Complexity of printing all root to leaf paths in binary tree

In, the code for printing root to leaf for every leaf node is provided below.

They state the algorithm is O(n), but I think it should be O(n log n) where n is the number of nodes. A standard DFS is typically O(n + E), but printing the paths seems to add a log n. Suppose h is the height of the perfect binary tree. There are n/2 nodes on the last level, hence n/2 paths that we need to print. Each path has h + 1 (let's just say it's h for mathematical simplicity) nodes. So we need end up printing h * n/2 nodes when printing all the paths. We know h = log2(n). So h * n/2 = O(n log n)?

Is their answer wrong, or is there something wrong with my analysis here?

#include <iostream>
#include <vector>
using namespace std;
// Data structure to store a binary tree node
struct Node
    int data;
    Node *left, *right;
    Node(int data)
        this->data = data;
        this->left = this->right = nullptr;
// Function to check if a given node is a leaf node or not
bool isLeaf(Node* node) {
    return (node->left == nullptr && node->right == nullptr);
// Recursive function to find paths from the root node to every leaf node
void printRootToleafPaths(Node* node, vector<int> &path)
    // base case
    if (node == nullptr) {
    // include the current node to the path
    // if a leaf node is found, print the path
    if (isLeaf(node))
        for (int data: path) {
            cout << data << " ";
        cout << endl;
    // recur for the left and right subtree
    printRootToleafPaths(node->left, path);
    printRootToleafPaths(node->right, path);
    // backtrack: remove the current node after the left, and right subtree are done
// The main function to print paths from the root node to every leaf node
void printRootToleafPaths(Node* node)
    // vector to store root-to-leaf path
    vector<int> path;
    printRootToleafPaths(node, path);
int main()
    /* Construct the following tree
            /   \
           /     \
          2       3
         / \     / \
        4   5   6   7
               /     \
              8       9
    Node* root = new Node(1);
    root->left = new Node(2);
    root->right = new Node(3);
    root->left->left = new Node(4);
    root->left->right = new Node(5);
    root->right->left = new Node(6);
    root->right->right = new Node(7);
    root->right->left->left = new Node(8);
    root->right->right->right = new Node(9);
    // print all root-to-leaf paths
    return 0;

Read more here:

Content Attribution

This content was originally published by roulette01 at Recent Questions - Stack Overflow, and is syndicated here via their RSS feed. You can read the original post over there.

%d bloggers like this: