Complexity of printing all root to leaf paths in binary tree

In https://www.techiedelight.com/print-all-paths-from-root-to-leaf-nodes-binary-tree/, 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) {
        return;
    }
 
    // include the current node to the path
    path.push_back(node->data);
 
    // 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
    path.pop_back();
}
 
// 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
              1
            /   \
           /     \
          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
    printRootToleafPaths(root);
 
    return 0;
}


Read more here: https://stackoverflow.com/questions/68477758/complexity-of-printing-all-root-to-leaf-paths-in-binary-tree

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: