Traversal Speed Comparison of BFS and DFS in Balanced and Skewed Binary Trees

Notice

This is an unedited manuscript accepted for publication and provided as an Article in Press for early access at the author’s request. The article will undergo copyediting, typesetting, and galley proof review before final publication. Please be aware that errors may be identified during production that could affect the content. All legal disclaimers of the journal apply.

Year : 2026 | Volume : 04 | 02 | Page :
    By

    Anand Singh,

  • Abhinav Singh,

  • Padma Mishra,

  1. Research Scholar, Department of MCA, Thakur Institute of Management Studies, Career Development & Research (TIMSCDR) Mumbai, Maharashtra, India
  2. Research Scholar, Department of MCA, Thakur Institute of Management Studies, Career Development & Research (TIMSCDR) Mumbai, Maharashtra, India
  3. Associate Professor, Department of MCA, Thakur Institute of Management Studies, Career Development & Research (TIMSCDR) Mumbai, Maharashtra, India

Abstract

In this paper, we provide an analysis of how well both breadth-first search (BFS) and depth-first search (DFS) algorithms perform while wandering through two kinds of binary trees: balanced and skewed. The research was motivated by the practical application of storing files and directories in a certain type of parent-child relationship through the use of hierarchical file systems (e.g., windows explorer). The result of measuring how fast and versatilely these data structures can be traversed has a direct influence on the amount of time needed to index and retrieve files from these types of directory structures. Both algorithms were implemented in Python from scratch to ensure fairness in comparison. To test their behavior, artificial binary trees of different sizes were created — some balanced, where nodes are evenly distributed, and others left-skewed, where all nodes lean to one side. During traversal, each node visit represented an indexing step that captured file metadata, simulating real- world behavior. The time taken for these traversals was measured precisely using the time.perf_counter() function, and multiple trials were conducted to ensure consistent results. O(n), signifying every node gets visited exactly once; however, the actual performance varies as to the structure of the tree. For instance, in a balanced tree, while BFS may require additional memory usage (it must maintain tracked nodes for each level within the queues that it utilizes), this essentially reduces the efficiency of using BFS over DFS. Due to better utilization of the system’s memory cache (especially regarding iterative DFS), DFS will outperform BFS when operating within a balanced tree. On the other hand, when working with a skewed tree, DFS becomes the superior algorithm because it eliminates the need for maintaining a large queue, thus reducing the overall overhead of the process. Overall, it has demonstrated superior performance and memory management abilities for indexing file systems. Keywords—BFS, DFS, Binary Tree, Balanced Tree, Skewed Tree, File System Indexing, Python, Algorithm Performance.

Keywords: BFS, DFS, Binary Tree, Balanced Tree, Skewed Tree, File System Indexing, Python, Algorithm Performance.

How to cite this article:
Anand Singh, Abhinav Singh, Padma Mishra. Traversal Speed Comparison of BFS and DFS in Balanced and Skewed Binary Trees. International Journal of Data Structure Studies. 2026; 04(02):-.
How to cite this URL:
Anand Singh, Abhinav Singh, Padma Mishra. Traversal Speed Comparison of BFS and DFS in Balanced and Skewed Binary Trees. International Journal of Data Structure Studies. 2026; 04(02):-. Available from: https://journals.stmjournals.com/ijdss/article=2026/view=247725


References

  1. Cormen TH, Leiserson CE, Rivest RL, Stein C. Introduction to Algorithms. 4th ed. Cambridge (MA): MIT Press; 2022.
  2. Dasgupta S, Papadimitriou CH, Vazirani U. Algorithms. New York (NY): McGraw-Hill; 2008.
  3. Weiss MA. Data Structures and Algorithm Analysis in C++. 4th ed. Boston (MA): Pearson; 2014.
  4. Sedgewick R, Wayne K. Algorithms. 4th ed. Boston (MA): Addison-Wesley; 2011.
  5. Brassard G, Bratley P. Fundamentals of Algorithmics. Englewood Cliffs (NJ): Prentice Hall; 1996.
  6. Mehlhorn K, Sanders P. Algorithms and Data Structures: The Basic Toolbox. Berlin: Springer; 2008.
  7. Meijer L, de Lara E. Performance analysis of breadth-first and depth-first search algorithms on tree structures. Int J Comput Appl. 2023;182(42):21-27.
  8. Patel H, Shah M. Comparative study of BFS and DFS traversal algorithms in graph and tree structures. J Emerg Technol Innov Res. 2023;10(2):45-50.
  9. Kumar P, Sinha S. Optimized file system search using BFS and DFS algorithms. Int J Adv Comput Sci Appl. 2022;13(11):512-519.
  10. Chowdhury MF, Rahman R. Evaluating the performance of tree traversal algorithms on unbalanced data structures. IEEE Access. 2021;9:118732-118742.
  11. Singh S, Verma D. A performance comparison between BFS and DFS for file indexing and search systems. Procedia Comput Sci. 2023;217:183-192.
  12. Jha PR. Impact of tree balance on search and traversal efficiency. Int J Inf Technol Syst. 2024;15(3):97-105.
  13. Yadav SK. Traversal efficiency analysis in binary trees using Python. Int J Res Eng Comput Sci. 2022;9(8):411-420.
  14. Gupta R, Sharma A. Performance optimization of recursive and iterative DFS implementations. In: Proceedings of the International Conference on Computational Intelligence and Data Science (ICCIDS); 2021. p. 350-356.
  15. Python Software Foundation. Python 3.12 documentation [Internet]. 2024 [cited 2026 Jun 26]. Available from: https://docs.python.org/3/
  16. McKinney W. Data structures for statistical computing in Python. In: Proceedings of the 9th Python in Science Conference; 2010. p. 56-61.
  17. Lutz M. Learning Python. 5th ed. Sebastopol (CA): O’Reilly Media; 2013.
  18. Dean J, Ghemawat S. MapReduce: Simplified data processing on large clusters. Commun ACM. 2008;51(1):107-113.
  19. Gupta, Raj K. Traversal strategies for hierarchical data indexing systems. ACM Comput Surv. 2023;55(9):1-28.
  20. Singh ND. Comparative evaluation of graph traversal techniques in large-scale data environments. IEEE Trans Knowl Data Eng. 2024;36(7):1450-1461.
  21. Gerela P. Study on data visualization: Its importance in the education sector. Int J Health Sci. 2022;6(NS3):6298-6305. doi:10.53730/ijhs.v6ns3.7393.
  22. Nagarkar S, Mishra P, Gaikwad V. Factors at play: Investigating the dimensions of privacy and security in smart home environments. Educ Adm Theory Pract. 2024;30(5):3197-3203. doi:10.53555/kuey.v30i5.3414.
  23. Mishra P, Nagarkar S, Gaikwad V. Integrating variable rate application with machine learning algorithms for intelligent and responsive agriculture. J Tech Educ. 2024;55.
  24. Basavaraj GN. Machine learning-enhanced direction-of-arrival estimation for coherent and non-coherent sources. Eng Technol Appl Sci Res. 2025;15(2):20647-20652.
  25. Ahmad E, Dash B, Tripathi A, et al. Hybrid CNN and image processing framework for precise characterization of cracks in concrete structures. Asian J Civ Eng. 2026;27:815-828. doi:10.1007/s42107-025-01535-0.
Ahead of Print Subscription Original Research
Volume 04
02
Received 10/03/2026
Accepted 09/06/2026
Published 26/06/2026
Publication Time 108 Days
1

Login


My IP

PlumX Metrics